xref: /XiangShan/src/main/scala/xiangshan/mem/lsqueue/FreeList.scala (revision 5003e6f8af8c3020e83ed43708fab7efc0816e54)
1e4f69d78Ssfencevma/***************************************************************************************
2e4f69d78Ssfencevma* Copyright (c) 2020-2021 Institute of Computing Technology, Chinese Academy of Sciences
3e4f69d78Ssfencevma* Copyright (c) 2020-2021 Peng Cheng Laboratory
4e4f69d78Ssfencevma*
5e4f69d78Ssfencevma* XiangShan is licensed under Mulan PSL v2.
6e4f69d78Ssfencevma* You can use this software according to the terms and conditions of the Mulan PSL v2.
7e4f69d78Ssfencevma* You may obtain a copy of Mulan PSL v2 at:
8e4f69d78Ssfencevma*          http://license.coscl.org.cn/MulanPSL2
9e4f69d78Ssfencevma*
10e4f69d78Ssfencevma* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
11e4f69d78Ssfencevma* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
12e4f69d78Ssfencevma* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
13e4f69d78Ssfencevma*
14e4f69d78Ssfencevma* See the Mulan PSL v2 for more details.
15e4f69d78Ssfencevma***************************************************************************************/
16e4f69d78Ssfencevmapackage xiangshan.mem
17e4f69d78Ssfencevma
188891a219SYinan Xuimport org.chipsalliance.cde.config.Parameters
19e4f69d78Ssfencevmaimport chisel3._
20e4f69d78Ssfencevmaimport chisel3.util._
21e4f69d78Ssfencevmaimport utils._
22e4f69d78Ssfencevmaimport utility._
23e4f69d78Ssfencevmaimport xiangshan._
24e4f69d78Ssfencevma
25e4f69d78Ssfencevmaclass FreeList(size: Int, allocWidth: Int, freeWidth: Int, enablePreAlloc: Boolean = false, moduleName: String = "")(implicit p: Parameters) extends XSModule
26e4f69d78Ssfencevma  with HasCircularQueuePtrHelper
27e4f69d78Ssfencevma  with HasPerfEvents
28e4f69d78Ssfencevma{
29e4f69d78Ssfencevma  val io = IO(new Bundle() {
30e4f69d78Ssfencevma    val allocateReq = Input(Vec(allocWidth, Bool()))
31e4f69d78Ssfencevma    val allocateSlot = Output(Vec(allocWidth, UInt()))
32e4f69d78Ssfencevma    val canAllocate = Output(Vec(allocWidth, Bool()))
33e4f69d78Ssfencevma    val doAllocate = Input(Vec(allocWidth, Bool()))
34e4f69d78Ssfencevma
35e4f69d78Ssfencevma    val free = Input(UInt(size.W))
36e4f69d78Ssfencevma
37e4f69d78Ssfencevma    val validCount = Output(UInt())
38e4f69d78Ssfencevma    val empty = Output(Bool())
39e4f69d78Ssfencevma  })
40e4f69d78Ssfencevma
41e4f69d78Ssfencevma  println(s"FreeList: $moduleName, size " + size)
42e4f69d78Ssfencevma
43e4f69d78Ssfencevma  val freeList = RegInit(VecInit(
44e4f69d78Ssfencevma    // originally {0, 1, ..., size - 1} are free.
45e4f69d78Ssfencevma    Seq.tabulate(size)(i => i.U(log2Up(size).W))
46e4f69d78Ssfencevma  ))
47e4f69d78Ssfencevma
48e4f69d78Ssfencevma  class FreeListPtr extends CircularQueuePtr[FreeListPtr](size)
49e4f69d78Ssfencevma  object FreeListPtr {
50e4f69d78Ssfencevma    def apply(f: Boolean, v: Int): FreeListPtr = {
51e4f69d78Ssfencevma      val ptr = Wire(new FreeListPtr)
52e4f69d78Ssfencevma      ptr.flag := f.B
53e4f69d78Ssfencevma      ptr.value := v.U
54e4f69d78Ssfencevma      ptr
55e4f69d78Ssfencevma    }
56e4f69d78Ssfencevma  }
57e4f69d78Ssfencevma
58e4f69d78Ssfencevma  val headPtr  = RegInit(FreeListPtr(false, 0))
59e4f69d78Ssfencevma  val headPtrNext = Wire(new FreeListPtr)
60e4f69d78Ssfencevma  val tailPtr = RegInit(FreeListPtr(true, 0))
61e4f69d78Ssfencevma  val tailPtrNext = Wire(new FreeListPtr)
62e4f69d78Ssfencevma
63e4f69d78Ssfencevma  // legality check
64e4f69d78Ssfencevma  def getRemBits(input: UInt)(rem: Int): UInt = {
65e4f69d78Ssfencevma    VecInit((0 until size / freeWidth).map(i => { input(freeWidth * i + rem) })).asUInt
66e4f69d78Ssfencevma  }
67e4f69d78Ssfencevma
68e4f69d78Ssfencevma  // free logic
69e4f69d78Ssfencevma  val freeMask = RegInit(0.U(size.W))
70e4f69d78Ssfencevma  val freeSelMask = Wire(UInt(size.W))
71e4f69d78Ssfencevma  val freeSelMaskVec = Wire(Vec(freeWidth, UInt(size.W)))
72e4f69d78Ssfencevma
73e4f69d78Ssfencevma  // update freeMask
74caaadfbeSsfencevma  require((size % freeWidth) == 0)
75e4f69d78Ssfencevma  freeSelMask := freeSelMaskVec.reduce(_|_)
76e4f69d78Ssfencevma  freeMask := (io.free | freeMask) & ~freeSelMask
77e4f69d78Ssfencevma
78e4f69d78Ssfencevma  val remFreeSelMaskVec = VecInit(Seq.tabulate(freeWidth)(rem => getRemBits((freeMask & ~freeSelMask))(rem)))
79caaadfbeSsfencevma  val remFreeSelIndexOHVec = VecInit(Seq.tabulate(freeWidth)(fport => {
80caaadfbeSsfencevma    val highIndexOH = PriorityEncoderOH(remFreeSelMaskVec(fport))
81caaadfbeSsfencevma    val freeIndexOHVec = Wire(Vec(size, Bool()))
82caaadfbeSsfencevma    freeIndexOHVec.foreach(e => e := false.B)
83caaadfbeSsfencevma    for (i <- 0 until size / freeWidth) {
84caaadfbeSsfencevma      freeIndexOHVec(i * freeWidth + fport) := highIndexOH(i)
85caaadfbeSsfencevma    }
86caaadfbeSsfencevma    freeIndexOHVec.asUInt
87e4f69d78Ssfencevma  }))
88e4f69d78Ssfencevma
89*5003e6f8SHuijin Li  val freeReq = GatedRegNext(VecInit(remFreeSelMaskVec.map(_.asUInt.orR)))
90*5003e6f8SHuijin Li  val freeSlotOH = GatedRegNext(remFreeSelIndexOHVec)
91e4f69d78Ssfencevma  val doFree = freeReq.asUInt.orR
92e4f69d78Ssfencevma
93e4f69d78Ssfencevma  for (i <- 0 until freeWidth) {
94e4f69d78Ssfencevma    val offset = PopCount(freeReq.take(i))
95e4f69d78Ssfencevma    val enqPtr = tailPtr + offset
96e4f69d78Ssfencevma
97e4f69d78Ssfencevma    when (freeReq(i)) {
98caaadfbeSsfencevma      freeList(enqPtr.value) := OHToUInt(freeSlotOH(i))
99e4f69d78Ssfencevma    }
100e4f69d78Ssfencevma
101caaadfbeSsfencevma    freeSelMaskVec(i) := Mux(freeReq(i), freeSlotOH(i), 0.U)
102e4f69d78Ssfencevma  }
103e4f69d78Ssfencevma
104e4f69d78Ssfencevma  tailPtrNext := tailPtr + PopCount(freeReq)
105e4f69d78Ssfencevma  tailPtr := Mux(doFree, tailPtrNext, tailPtr)
106e4f69d78Ssfencevma
107e4f69d78Ssfencevma  // allocate
108e4f69d78Ssfencevma  val doAllocate = io.doAllocate.asUInt.orR
109e4f69d78Ssfencevma  val numAllocate = PopCount(io.doAllocate)
110e4f69d78Ssfencevma  val freeSlotCnt = RegInit(size.U(log2Up(size + 1).W))
111e4f69d78Ssfencevma
112e4f69d78Ssfencevma  for (i <- 0 until allocWidth) {
113e4f69d78Ssfencevma    val offset = PopCount(io.allocateReq.take(i))
114e4f69d78Ssfencevma
115e4f69d78Ssfencevma    if (enablePreAlloc) {
116e4f69d78Ssfencevma      val deqPtr = headPtr + numAllocate + offset
117577fcf2aSZhaoyang You      io.canAllocate(i) := RegEnable(isBefore(deqPtr, tailPtr), enablePreAlloc.B)
118577fcf2aSZhaoyang You      io.allocateSlot(i) := RegEnable(freeList(deqPtr.value), enablePreAlloc.B)
119e4f69d78Ssfencevma    } else {
120e4f69d78Ssfencevma      val deqPtr = headPtr + offset
121e4f69d78Ssfencevma      io.canAllocate(i) := isBefore(deqPtr, tailPtr)
122e4f69d78Ssfencevma      io.allocateSlot(i) := freeList(deqPtr.value)
123e4f69d78Ssfencevma    }
124e4f69d78Ssfencevma
125e4f69d78Ssfencevma  }
126e4f69d78Ssfencevma
127e4f69d78Ssfencevma  headPtrNext := headPtr + numAllocate
128e4f69d78Ssfencevma  headPtr := Mux(doAllocate, headPtrNext, headPtr)
129e4f69d78Ssfencevma  freeSlotCnt := distanceBetween(tailPtrNext, headPtrNext)
130e4f69d78Ssfencevma
131e4f69d78Ssfencevma  io.empty := freeSlotCnt === 0.U
132e4f69d78Ssfencevma  io.validCount := size.U - freeSlotCnt
133e4f69d78Ssfencevma
134e4f69d78Ssfencevma  XSPerfAccumulate("empty", io.empty)
135e4f69d78Ssfencevma  val perfEvents: Seq[(String, UInt)] = Seq(
136e4f69d78Ssfencevma    ("empty", io.empty)
137e4f69d78Ssfencevma  )
138e4f69d78Ssfencevma  generatePerfEvent()
139e4f69d78Ssfencevma
140e4f69d78Ssfencevma  // unique check
141e4f69d78Ssfencevma  val enableFreeListCheck = false
142e4f69d78Ssfencevma  if (enableFreeListCheck) {
143e4f69d78Ssfencevma    val differentFlag = tailPtr.flag ^ headPtr.flag
144e4f69d78Ssfencevma    val headMask = UIntToMask(headPtr.value, size)
145e4f69d78Ssfencevma    val tailMask = UIntToMask(tailPtr.value, size)
146e4f69d78Ssfencevma    val validMask1 = Mux(differentFlag, ~tailMask, tailMask ^ headMask)
147e4f69d78Ssfencevma    val validMask2 = Mux(differentFlag, headMask, 0.U(size.W))
148e4f69d78Ssfencevma    val validMask = ~(validMask1 | validMask2)
149e4f69d78Ssfencevma    for (i <- 0 until size) {
150e4f69d78Ssfencevma      for (j <- i+1 until size) {
151e4f69d78Ssfencevma        if (i != j) {
152e4f69d78Ssfencevma          XSError(validMask(i) && validMask(j) && freeList(i) === freeList(j),s"Found same entry in free list! (i=$i j=$j)\n")
153e4f69d78Ssfencevma        }
154e4f69d78Ssfencevma      }
155e4f69d78Ssfencevma    }
156e4f69d78Ssfencevma  }
157e4f69d78Ssfencevma
158e4f69d78Ssfencevma  // end
159e4f69d78Ssfencevma}