1  from functools import reduce
  2  import operator
  3  from amaranth import *
  4  from transactron import Method, Methods, Transaction, def_method, TModule, def_methods
  5  from transactron.lib.fifo import WideFifo
  6  from transactron.lib import logging
  7  from transactron.lib.metrics import *
  8  from coreblocks.interface.layouts import ROBLayouts
  9  from coreblocks.params import GenParams
 10  
 11  __all__ = ["ReorderBuffer"]
 12  
 13  log = logging.HardwareLogger("core_structs.rob")
 14  
 15  
 16  class ReorderBuffer(Elaboratable):
 17      """Reorder buffer.
 18  
 19      The reorder buffer (ROB) is a data structure responsible for preserving
 20      the original instruction order for the purpose of correctly freeing
 21      allocated registers and exception handling. The ROB is essentially
 22      a FIFO queue: the instructions are added to it in order by the scheduler
 23      (a part of the frontend) and removed in order by the retirement module
 24      (a part of the backend). Additionally, the ROB remembers which
 25      instructions finished execution: this information is updated by the
 26      announcement module.
 27  
 28      Attributes
 29      ----------
 30      put : Method
 31          Inserts instructions into the ROB. Used by the scheduler.
 32      mark_done : Methods
 33          Marks instruction as completed. Used by the announcement module.
 34      retire : Method
 35          Removes instructions from the ROB. Used by the retirement module.
 36      peek : Method
 37          Returns the front of the ROB without removing instructions.
 38      get_indices : Method
 39          Returns the `rob_id` of the oldest instruction in the ROB and the
 40          first `rob_id` after the newest instruction in the ROB.
 41      """
 42  
 43      def __init__(self, gen_params: GenParams, mark_done_ports: int) -> None:
 44          """
 45          Parameters
 46          ----------
 47          gen_params : GenParams
 48              Core generator parameters for the selected core configuration.
 49          mark_done_ports : int
 50              The number of `mark_done` methods (announcement ports).
 51          """
 52          self.params = gen_params
 53          layouts = gen_params.get(ROBLayouts)
 54          self.put = Method(i=layouts.put_layout, o=layouts.put_out_layout)
 55          self.mark_done = Methods(mark_done_ports, i=layouts.mark_done_layout)
 56          self.peek = Method(o=layouts.peek_layout)
 57          self.retire = Method(i=layouts.retire_layout)
 58          self.done = Array(Signal() for _ in range(2**self.params.rob_entries_bits))
 59          self.exception = Array(Signal() for _ in range(2**self.params.rob_entries_bits))
 60          self.data = WideFifo(
 61              shape=layouts.data_layout,
 62              depth=2**self.params.rob_entries_bits,
 63              read_width=self.params.retirement_superscalarity,
 64              write_width=self.params.frontend_superscalarity,
 65          )
 66          self.get_indices = Method(o=layouts.get_indices)
 67  
 68          self.perf_rob_wait_time = WideFIFOLatencyMeasurer(
 69              "backend.rob.wait_time",
 70              description="Distribution of time instructions spend in ROB",
 71              slots_number=(2**gen_params.rob_entries_bits + 1),
 72              max_latency=1000,
 73              max_start_count=gen_params.frontend_superscalarity,
 74              max_stop_count=gen_params.retirement_superscalarity,
 75          )
 76          self.perf_rob_size = HwExpHistogram(
 77              "backend.rob.size",
 78              description="Number of instructions in ROB",
 79              bucket_count=gen_params.rob_entries_bits + 1,
 80              sample_width=gen_params.rob_entries_bits,
 81          )
 82          self.perf_rob_put_count = TaggedCounter(
 83              "backend.rob.put_count",
 84              description="Number of instructions inserted into ROB in one cycle",
 85              tags=range(gen_params.frontend_superscalarity + 1),
 86          )
 87          self.perf_rob_retire_count = TaggedCounter(
 88              "backend.rob.retire_count",
 89              description="Number of instructions removed from ROB in one cycle",
 90              tags=range(gen_params.retirement_superscalarity + 1),
 91          )
 92  
 93      def elaborate(self, platform):
 94          m = TModule()
 95  
 96          m.submodules += [
 97              self.perf_rob_wait_time,
 98              self.perf_rob_size,
 99              self.perf_rob_put_count,
100              self.perf_rob_retire_count,
101          ]
102  
103          start_idx = Value.cast(self.data.read_idx)
104          end_idx = Value.cast(self.data.write_idx)
105  
106          start_idx_plus = [Signal.like(start_idx) for _ in range(self.params.retirement_superscalarity)]
107          for i in range(len(start_idx_plus)):
108              m.d.comb += start_idx_plus[i].eq(start_idx + i)
109  
110          m.submodules.data = self.data
111  
112          with Transaction().body(m):
113              peek_ret = self.data.peek(m)
114  
115          @def_method(m, self.peek, nonexclusive=True)
116          def _():
117              entries = []
118              for i in range(self.params.retirement_superscalarity):
119                  entries.append(
120                      {
121                          "rob_data": peek_ret.data[i],
122                          "rob_id": start_idx_plus[i],
123                          "exception": self.exception[start_idx_plus[i]],
124                      }
125                  )
126              return {"count": peek_ret.count, "entries": entries}
127  
128          @def_method(m, self.retire, ready=self.done[start_idx])
129          def _(count: int):
130              retire_ok = reduce(
131                  operator.and_,
132                  [self.done[start_idx_plus[i]] | (i >= count) for i in range(self.params.retirement_superscalarity)],
133              )
134              log.assertion(m, (count <= peek_ret.count) & retire_ok, "retire called with invalid count {}", count)
135              self.perf_rob_wait_time.stop(m, count=count)
136              self.perf_rob_retire_count.incr(m, tag=count)
137              self.data.read(m, count=count)
138              for i in range(self.params.retirement_superscalarity):
139                  with m.If(i < count):
140                      m.d.sync += self.done[start_idx_plus[i]].eq(0)
141  
142          @def_method(m, self.put)
143          def _(count: int, entries):
144              self.perf_rob_wait_time.start(m, count=count)
145              self.perf_rob_put_count.incr(m, tag=count)
146              self.data.write(m, count=count, data=entries)
147              entries = []
148              for i in range(self.params.frontend_superscalarity):
149                  rob_id = (end_idx + i)[: len(end_idx)]
150                  entries.append({"rob_id": rob_id})
151              return {"entries": entries}
152  
153          # TODO: There is a potential race condition when ROB is flushed.
154          # If functional units aren't flushed, finished obsolete instructions
155          # could mark fields in ROB as done when they shouldn't.
156          @def_methods(m, self.mark_done)
157          def _(k: int, rob_id: Value, exception):
158              log.assertion(m, ~self.done[rob_id], "mark_done called on already done ROB entry {}", rob_id)
159              m.d.sync += self.done[rob_id].eq(1)
160              m.d.sync += self.exception[rob_id].eq(exception)
161  
162          @def_method(m, self.get_indices, nonexclusive=True)
163          def _():
164              return {"start": start_idx, "end": end_idx}
165  
166          if self.perf_rob_size.metrics_enabled():
167              rob_size = Signal(self.params.rob_entries_bits)
168              m.d.comb += rob_size.eq((end_idx - start_idx)[0 : self.params.rob_entries_bits])
169              with Transaction(name="perf").body(m):
170                  self.perf_rob_size.add(m, rob_size)
171  
172          return m