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}