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