nmigen/lib/fifo.py

   1 """First-in first-out queues."""
   2
   3 from .. import *
   4 from ..asserts import *
   5 from .._utils import log2_int, deprecated
   6 from .coding import GrayEncoder, GrayDecoder
   7 from .cdc import FFSynchronizer, AsyncFFSynchronizer
   8
   9
  10 __all__ = ["FIFOInterface", "SyncFIFO", "SyncFIFOBuffered", "AsyncFIFO", "AsyncFIFOBuffered"]
  11
  12
  13 class FIFOInterface:
  14     _doc_template = """
  15     {description}
  16
  17     Parameters
  18     ----------
  19     width : int
  20         Bit width of data entries.
  21     depth : int
  22         Depth of the queue. If zero, the FIFO cannot be read from or written to.
  23     {parameters}
  24
  25     Attributes
  26     ----------
  27     {attributes}
  28     w_data : in, width
  29         Input data.
  30     w_rdy : out
  31         Asserted if there is space in the queue, i.e. ``w_en`` can be asserted to write
  32         a new entry.
  33     w_en : in
  34         Write strobe. Latches ``w_data`` into the queue. Does nothing if ``w_rdy`` is not asserted.
  35     w_level : out
  36         Number of unread entries.
  37     {w_attributes}
  38     r_data : out, width
  39         Output data. {r_data_valid}
  40     r_rdy : out
  41         Asserted if there is an entry in the queue, i.e. ``r_en`` can be asserted to read
  42         an existing entry.
  43     r_en : in
  44         Read strobe. Makes the next entry (if any) available on ``r_data`` at the next cycle.
  45         Does nothing if ``r_rdy`` is not asserted.
  46     r_level : out
  47         Number of unread entries.
  48     {r_attributes}
  49     """
  50
  51     __doc__ = _doc_template.format(description="""
  52     Data written to the input interface (``w_data``, ``w_rdy``, ``w_en``) is buffered and can be
  53     read at the output interface (``r_data``, ``r_rdy``, ``r_en`). The data entry written first
  54     to the input also appears first on the output.
  55     """,
  56     parameters="",
  57     r_data_valid="The conditions in which ``r_data`` is valid depends on the type of the queue.",
  58     attributes="""
  59     fwft : bool
  60         First-word fallthrough. If set, when ``r_rdy`` rises, the first entry is already
  61         available, i.e. ``r_data`` is valid. Otherwise, after ``r_rdy`` rises, it is necessary
  62         to strobe ``r_en`` for ``r_data`` to become valid.
  63     """.strip(),
  64     w_attributes="",
  65     r_attributes="")
  66
  67     def __init__(self, *, width, depth, fwft):
  68         if not isinstance(width, int) or width < 0:
  69             raise TypeError("FIFO width must be a non-negative integer, not {!r}"
  70                             .format(width))
  71         if not isinstance(depth, int) or depth < 0:
  72             raise TypeError("FIFO depth must be a non-negative integer, not {!r}"
  73                             .format(depth))
  74         self.width = width
  75         self.depth = depth
  76         self.fwft  = fwft
  77
  78         self.w_data = Signal(width, reset_less=True)
  79         self.w_rdy  = Signal() # writable; not full
  80         self.w_en   = Signal()
  81         self.w_level = Signal(range(depth + 1))
  82
  83         self.r_data = Signal(width, reset_less=True)
  84         self.r_rdy  = Signal() # readable; not empty
  85         self.r_en   = Signal()
  86         self.r_level = Signal(range(depth + 1))
  87
  88
  89 def _incr(signal, modulo):
  90     if modulo == 2 ** len(signal):
  91         return signal + 1
  92     else:
  93         return Mux(signal == modulo - 1, 0, signal + 1)
  94
  95
  96 class SyncFIFO(Elaboratable, FIFOInterface):
  97     __doc__ = FIFOInterface._doc_template.format(
  98     description="""
  99     Synchronous first in, first out queue.
 100
 101     Read and write interfaces are accessed from the same clock domain. If different clock domains
 102     are needed, use :class:`AsyncFIFO`.
 103     """.strip(),
 104     parameters="""
 105     fwft : bool
 106         First-word fallthrough. If set, when the queue is empty and an entry is written into it,
 107         that entry becomes available on the output on the same clock cycle. Otherwise, it is
 108         necessary to assert ``r_en`` for ``r_data`` to become valid.
 109     """.strip(),
 110     r_data_valid="""
 111     For FWFT queues, valid if ``r_rdy`` is asserted. For non-FWFT queues, valid on the next
 112     cycle after ``r_rdy`` and ``r_en`` have been asserted.
 113     """.strip(),
 114     attributes="",
 115     r_attributes="",
 116     w_attributes="")
 117
 118     def __init__(self, *, width, depth, fwft=True):
 119         super().__init__(width=width, depth=depth, fwft=fwft)
 120
 121         self.level = Signal(range(depth + 1))
 122
 123     def elaborate(self, platform):
 124         m = Module()
 125         if self.depth == 0:
 126             m.d.comb += [
 127                 self.w_rdy.eq(0),
 128                 self.r_rdy.eq(0),
 129             ]
 130             return m
 131
 132         m.d.comb += [
 133             self.w_rdy.eq(self.level != self.depth),
 134             self.r_rdy.eq(self.level != 0),
 135             self.w_level.eq(self.level),
 136             self.r_level.eq(self.level),
 137         ]
 138
 139         do_read  = self.r_rdy & self.r_en
 140         do_write = self.w_rdy & self.w_en
 141
 142         storage = Memory(width=self.width, depth=self.depth)
 143         w_port  = m.submodules.w_port = storage.write_port()
 144         r_port  = m.submodules.r_port = storage.read_port(
 145             domain="comb" if self.fwft else "sync", transparent=self.fwft)
 146         produce = Signal(range(self.depth))
 147         consume = Signal(range(self.depth))
 148
 149         m.d.comb += [
 150             w_port.addr.eq(produce),
 151             w_port.data.eq(self.w_data),
 152             w_port.en.eq(self.w_en & self.w_rdy),
 153         ]
 154         with m.If(do_write):
 155             m.d.sync += produce.eq(_incr(produce, self.depth))
 156
 157         m.d.comb += [
 158             r_port.addr.eq(consume),
 159             self.r_data.eq(r_port.data),
 160         ]
 161         if not self.fwft:
 162             m.d.comb += r_port.en.eq(self.r_en)
 163         with m.If(do_read):
 164             m.d.sync += consume.eq(_incr(consume, self.depth))
 165
 166         with m.If(do_write & ~do_read):
 167             m.d.sync += self.level.eq(self.level + 1)
 168         with m.If(do_read & ~do_write):
 169             m.d.sync += self.level.eq(self.level - 1)
 170
 171         if platform == "formal":
 172             # TODO: move this logic to SymbiYosys
 173             with m.If(Initial()):
 174                 m.d.comb += [
 175                     Assume(produce < self.depth),
 176                     Assume(consume < self.depth),
 177                 ]
 178                 with m.If(produce == consume):
 179                     m.d.comb += Assume((self.level == 0) | (self.level == self.depth))
 180                 with m.If(produce > consume):
 181                     m.d.comb += Assume(self.level == (produce - consume))
 182                 with m.If(produce < consume):
 183                     m.d.comb += Assume(self.level == (self.depth + produce - consume))
 184             with m.Else():
 185                 m.d.comb += [
 186                     Assert(produce < self.depth),
 187                     Assert(consume < self.depth),
 188                 ]
 189                 with m.If(produce == consume):
 190                     m.d.comb += Assert((self.level == 0) | (self.level == self.depth))
 191                 with m.If(produce > consume):
 192                     m.d.comb += Assert(self.level == (produce - consume))
 193                 with m.If(produce < consume):
 194                     m.d.comb += Assert(self.level == (self.depth + produce - consume))
 195
 196         return m
 197
 198
 199 class SyncFIFOBuffered(Elaboratable, FIFOInterface):
 200     __doc__ = FIFOInterface._doc_template.format(
 201     description="""
 202     Buffered synchronous first in, first out queue.
 203
 204     This queue's interface is identical to :class:`SyncFIFO` configured as ``fwft=True``, but it
 205     does not use asynchronous memory reads, which are incompatible with FPGA block RAMs.
 206
 207     In exchange, the latency between an entry being written to an empty queue and that entry
 208     becoming available on the output is increased by one cycle compared to :class:`SyncFIFO`.
 209     """.strip(),
 210     parameters="""
 211     fwft : bool
 212         Always set.
 213     """.strip(),
 214     attributes="",
 215     r_data_valid="Valid if ``r_rdy`` is asserted.",
 216     r_attributes="""
 217     level : out
 218         Number of unread entries.
 219     """.strip(),
 220     w_attributes="")
 221
 222     def __init__(self, *, width, depth):
 223         super().__init__(width=width, depth=depth, fwft=True)
 224
 225         self.level = Signal(range(depth + 1))
 226
 227     def elaborate(self, platform):
 228         m = Module()
 229         if self.depth == 0:
 230             m.d.comb += [
 231                 self.w_rdy.eq(0),
 232                 self.r_rdy.eq(0),
 233             ]
 234             return m
 235
 236         # Effectively, this queue treats the output register of the non-FWFT inner queue as
 237         # an additional storage element.
 238         m.submodules.unbuffered = fifo = SyncFIFO(width=self.width, depth=self.depth - 1,
 239                                                   fwft=False)
 240
 241         m.d.comb += [
 242             fifo.w_data.eq(self.w_data),
 243             fifo.w_en.eq(self.w_en),
 244             self.w_rdy.eq(fifo.w_rdy),
 245         ]
 246
 247         m.d.comb += [
 248             self.r_data.eq(fifo.r_data),
 249             fifo.r_en.eq(fifo.r_rdy & (~self.r_rdy | self.r_en)),
 250         ]
 251         with m.If(fifo.r_en):
 252             m.d.sync += self.r_rdy.eq(1)
 253         with m.Elif(self.r_en):
 254             m.d.sync += self.r_rdy.eq(0)
 255
 256         m.d.comb += [
 257             self.level.eq(fifo.level + self.r_rdy),
 258             self.w_level.eq(self.level),
 259             self.r_level.eq(self.level),
 260         ]
 261
 262         return m
 263
 264
 265 class AsyncFIFO(Elaboratable, FIFOInterface):
 266     __doc__ = FIFOInterface._doc_template.format(
 267     description="""
 268     Asynchronous first in, first out queue.
 269
 270     Read and write interfaces are accessed from different clock domains, which can be set when
 271     constructing the FIFO.
 272
 273     :class:`AsyncFIFO` can be reset from the write clock domain. When the write domain reset is
 274     asserted, the FIFO becomes empty. When the read domain is reset, data remains in the FIFO - the
 275     read domain logic should correctly handle this case.
 276
 277     :class:`AsyncFIFO` only supports power of 2 depths. Unless ``exact_depth`` is specified,
 278     the ``depth`` parameter is rounded up to the next power of 2.
 279     """.strip(),
 280     parameters="""
 281     r_domain : str
 282         Read clock domain.
 283     w_domain : str
 284         Write clock domain.
 285     """.strip(),
 286     attributes="""
 287     fwft : bool
 288         Always set.
 289     """.strip(),
 290     r_data_valid="Valid if ``r_rdy`` is asserted.",
 291     r_attributes="""
 292     r_rst : Signal, out
 293         Asserted while the FIFO is being reset by the write-domain reset (for at least one
 294         read-domain clock cycle).
 295     """.strip(),
 296     w_attributes="")
 297
 298     def __init__(self, *, width, depth, r_domain="read", w_domain="write", exact_depth=False):
 299         if depth != 0:
 300             try:
 301                 depth_bits = log2_int(depth, need_pow2=exact_depth)
 302                 depth = 1 << depth_bits
 303             except ValueError as e:
 304                 raise ValueError("AsyncFIFO only supports depths that are powers of 2; requested "
 305                                  "exact depth {} is not"
 306                                  .format(depth)) from None
 307         else:
 308             depth_bits = 0
 309         super().__init__(width=width, depth=depth, fwft=True)
 310
 311         self.r_rst = Signal()
 312         self._r_domain = r_domain
 313         self._w_domain = w_domain
 314         self._ctr_bits = depth_bits + 1
 315
 316     def elaborate(self, platform):
 317         m = Module()
 318         if self.depth == 0:
 319             m.d.comb += [
 320                 self.w_rdy.eq(0),
 321                 self.r_rdy.eq(0),
 322             ]
 323             return m
 324
 325         # The design of this queue is the "style #2" from Clifford E. Cummings' paper "Simulation
 326         # and Synthesis Techniques for Asynchronous FIFO Design":
 327         # http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO1.pdf
 328
 329         do_write = self.w_rdy & self.w_en
 330         do_read  = self.r_rdy & self.r_en
 331
 332         # TODO: extract this pattern into lib.cdc.GrayCounter
 333         produce_w_bin = Signal(self._ctr_bits)
 334         produce_w_nxt = Signal(self._ctr_bits)
 335         m.d.comb += produce_w_nxt.eq(produce_w_bin + do_write)
 336         m.d[self._w_domain] += produce_w_bin.eq(produce_w_nxt)
 337
 338         # Note: Both read-domain counters must be reset_less (see comments below)
 339         consume_r_bin = Signal(self._ctr_bits, reset_less=True)
 340         consume_r_nxt = Signal(self._ctr_bits)
 341         m.d.comb += consume_r_nxt.eq(consume_r_bin + do_read)
 342         m.d[self._r_domain] += consume_r_bin.eq(consume_r_nxt)
 343
 344         produce_w_gry = Signal(self._ctr_bits)
 345         produce_r_gry = Signal(self._ctr_bits)
 346         produce_enc = m.submodules.produce_enc = \
 347             GrayEncoder(self._ctr_bits)
 348         produce_cdc = m.submodules.produce_cdc = \
 349             FFSynchronizer(produce_w_gry, produce_r_gry, o_domain=self._r_domain)
 350         m.d.comb += produce_enc.i.eq(produce_w_nxt),
 351         m.d[self._w_domain] += produce_w_gry.eq(produce_enc.o)
 352
 353         consume_r_gry = Signal(self._ctr_bits, reset_less=True)
 354         consume_w_gry = Signal(self._ctr_bits)
 355         consume_enc = m.submodules.consume_enc = \
 356             GrayEncoder(self._ctr_bits)
 357         consume_cdc = m.submodules.consume_cdc = \
 358             FFSynchronizer(consume_r_gry, consume_w_gry, o_domain=self._w_domain)
 359         m.d.comb += consume_enc.i.eq(consume_r_nxt)
 360         m.d[self._r_domain] += consume_r_gry.eq(consume_enc.o)
 361
 362         consume_w_bin = Signal(self._ctr_bits)
 363         consume_dec = m.submodules.consume_dec = \
 364             GrayDecoder(self._ctr_bits)
 365         m.d.comb += consume_dec.i.eq(consume_w_gry),
 366         m.d[self._w_domain] += consume_w_bin.eq(consume_dec.o)
 367
 368         produce_r_bin = Signal(self._ctr_bits)
 369         produce_dec = m.submodules.produce_dec = \
 370             GrayDecoder(self._ctr_bits)
 371         m.d.comb += produce_dec.i.eq(produce_r_gry),
 372         m.d[self._r_domain] += produce_r_bin.eq(produce_dec.o)
 373
 374         w_full  = Signal()
 375         r_empty = Signal()
 376         m.d.comb += [
 377             w_full.eq((produce_w_gry[-1]  != consume_w_gry[-1]) &
 378                       (produce_w_gry[-2]  != consume_w_gry[-2]) &
 379                       (produce_w_gry[:-2] == consume_w_gry[:-2])),
 380             r_empty.eq(consume_r_gry == produce_r_gry),
 381         ]
 382
 383         m.d[self._w_domain] += self.w_level.eq((produce_w_bin - consume_w_bin)[:self._ctr_bits-1])
 384         m.d[self._r_domain] += self.r_level.eq((produce_r_bin - consume_r_bin)[:self._ctr_bits-1])
 385
 386         storage = Memory(width=self.width, depth=self.depth)
 387         w_port  = m.submodules.w_port = storage.write_port(domain=self._w_domain)
 388         r_port  = m.submodules.r_port = storage.read_port (domain=self._r_domain,
 389                                                            transparent=False)
 390         m.d.comb += [
 391             w_port.addr.eq(produce_w_bin[:-1]),
 392             w_port.data.eq(self.w_data),
 393             w_port.en.eq(do_write),
 394             self.w_rdy.eq(~w_full),
 395         ]
 396         m.d.comb += [
 397             r_port.addr.eq(consume_r_nxt[:-1]),
 398             self.r_data.eq(r_port.data),
 399             r_port.en.eq(1),
 400             self.r_rdy.eq(~r_empty),
 401         ]
 402
 403         # Reset handling to maintain FIFO and CDC invariants in the presence of a write-domain
 404         # reset.
 405         # There is a CDC hazard associated with resetting an async FIFO - Gray code counters which
 406         # are reset to 0 violate their Gray code invariant. One way to handle this is to ensure
 407         # that both sides of the FIFO are asynchronously reset by the same signal. We adopt a
 408         # slight variation on this approach - reset control rests entirely with the write domain.
 409         # The write domain's reset signal is used to asynchronously reset the read domain's
 410         # counters and force the FIFO to be empty when the write domain's reset is asserted.
 411         # This requires the two read domain counters to be marked as "reset_less", as they are
 412         # reset through another mechanism. See https://github.com/nmigen/nmigen/issues/181 for the
 413         # full discussion.
 414         w_rst = ResetSignal(domain=self._w_domain, allow_reset_less=True)
 415         r_rst = Signal()
 416
 417         # Async-set-sync-release synchronizer avoids CDC hazards
 418         rst_cdc = m.submodules.rst_cdc = \
 419             AsyncFFSynchronizer(w_rst, r_rst, domain=self._r_domain)
 420
 421         # Decode Gray code counter synchronized from write domain to overwrite binary
 422         # counter in read domain.
 423         rst_dec = m.submodules.rst_dec = \
 424             GrayDecoder(self._ctr_bits)
 425         m.d.comb += rst_dec.i.eq(produce_r_gry)
 426         with m.If(r_rst):
 427             m.d.comb += r_empty.eq(1)
 428             m.d[self._r_domain] += consume_r_gry.eq(produce_r_gry)
 429             m.d[self._r_domain] += consume_r_bin.eq(rst_dec.o)
 430             m.d[self._r_domain] += self.r_rst.eq(1)
 431         with m.Else():
 432             m.d[self._r_domain] += self.r_rst.eq(0)
 433
 434         if platform == "formal":
 435             with m.If(Initial()):
 436                 m.d.comb += Assume(produce_w_gry == (produce_w_bin ^ produce_w_bin[1:]))
 437                 m.d.comb += Assume(consume_r_gry == (consume_r_bin ^ consume_r_bin[1:]))
 438
 439         return m
 440
 441
 442 class AsyncFIFOBuffered(Elaboratable, FIFOInterface):
 443     __doc__ = FIFOInterface._doc_template.format(
 444     description="""
 445     Buffered asynchronous first in, first out queue.
 446
 447     Read and write interfaces are accessed from different clock domains, which can be set when
 448     constructing the FIFO.
 449
 450     :class:`AsyncFIFOBuffered` only supports power of 2 plus one depths. Unless ``exact_depth``
 451     is specified, the ``depth`` parameter is rounded up to the next power of 2 plus one.
 452     (The output buffer acts as an additional queue element.)
 453
 454     This queue's interface is identical to :class:`AsyncFIFO`, but it has an additional register
 455     on the output, improving timing in case of block RAM that has large clock-to-output delay.
 456
 457     In exchange, the latency between an entry being written to an empty queue and that entry
 458     becoming available on the output is increased by one cycle compared to :class:`AsyncFIFO`.
 459     """.strip(),
 460     parameters="""
 461     r_domain : str
 462         Read clock domain.
 463     w_domain : str
 464         Write clock domain.
 465     """.strip(),
 466     attributes="""
 467     fwft : bool
 468         Always set.
 469     """.strip(),
 470     r_data_valid="Valid if ``r_rdy`` is asserted.",
 471     r_attributes="""
 472     r_rst : Signal, out
 473         Asserted while the FIFO is being reset by the write-domain reset (for at least one
 474         read-domain clock cycle).
 475     """.strip(),
 476     w_attributes="")
 477
 478     def __init__(self, *, width, depth, r_domain="read", w_domain="write", exact_depth=False):
 479         if depth != 0:
 480             try:
 481                 depth_bits = log2_int(max(0, depth - 1), need_pow2=exact_depth)
 482                 depth = (1 << depth_bits) + 1
 483             except ValueError as e:
 484                 raise ValueError("AsyncFIFOBuffered only supports depths that are one higher "
 485                                  "than powers of 2; requested exact depth {} is not"
 486                                  .format(depth)) from None
 487         super().__init__(width=width, depth=depth, fwft=True)
 488
 489         self.r_rst = Signal()
 490         self._r_domain = r_domain
 491         self._w_domain = w_domain
 492
 493     def elaborate(self, platform):
 494         m = Module()
 495         if self.depth == 0:
 496             m.d.comb += [
 497                 self.w_rdy.eq(0),
 498                 self.r_rdy.eq(0),
 499             ]
 500             return m
 501
 502         m.submodules.unbuffered = fifo = AsyncFIFO(width=self.width, depth=self.depth - 1,
 503             r_domain=self._r_domain, w_domain=self._w_domain)
 504
 505         m.d.comb += [
 506             fifo.w_data.eq(self.w_data),
 507             self.w_rdy.eq(fifo.w_rdy),
 508             fifo.w_en.eq(self.w_en),
 509             self.w_level.eq(fifo.w_level),
 510         ]
 511
 512         with m.If(self.r_en | ~self.r_rdy):
 513             m.d[self._r_domain] += [
 514                 self.r_data.eq(fifo.r_data),
 515                 self.r_rdy.eq(fifo.r_rdy),
 516                 self.r_rst.eq(fifo.r_rst),
 517                 self.r_level.eq(fifo.r_level),
 518             ]
 519             m.d.comb += [
 520                 fifo.r_en.eq(1)
 521             ]
 522
 523         return m