xref: /XiangShan/src/main/scala/xiangshan/frontend/BPU.scala (revision 43c072e72d16eb5cd87286d2de02c5d70bfcaf3f) 
1package xiangshan.frontend
2
3import chisel3._
4import chisel3.util._
5import xiangshan._
6import utils._
7
8class TableAddr(val idxBits: Int, val banks: Int) extends XSBundle {
9  def tagBits = VAddrBits - idxBits - 2
10
11  val tag = UInt(tagBits.W)
12  val idx = UInt(idxBits.W)
13  val offset = UInt(2.W)
14
15  def fromUInt(x: UInt) = x.asTypeOf(UInt(VAddrBits.W)).asTypeOf(this)
16  def getTag(x: UInt) = fromUInt(x).tag
17  def getIdx(x: UInt) = fromUInt(x).idx
18  def getBank(x: UInt) = getIdx(x)(log2Up(banks) - 1, 0)
19  def getBankIdx(x: UInt) = getIdx(x)(idxBits - 1, log2Up(banks))
20}
21
22class BPU extends XSModule {
23  val io = IO(new Bundle() {
24    // val flush = Input(Bool())
25    // update bpu based on redirect signals from brq
26    val redirect = Flipped(ValidIO(new Redirect))
27    val in = new Bundle { val pc = Flipped(Valid(UInt(VAddrBits.W))) }
28    val predMask = Output(Vec(FetchWidth, Bool()))
29    val predTargets = Output(Vec(FetchWidth, UInt(VAddrBits.W)))
30  })
31
32  val flush = BoolStopWatch(io.redirect.valid, io.in.pc.valid, startHighPriority = true)
33
34  // BTB makes a quick prediction for branch and direct jump, which is
35  // 4-way set-associative, and each way is divided into 4 banks.
36  val btbAddr = new TableAddr(log2Up(BtbSets), BtbBanks)
37  def btbEntry() = new Bundle {
38    val valid = Bool()
39    // TODO: don't need full length of tag and target
40    val tag = UInt(btbAddr.tagBits.W)
41    val _type = UInt(2.W)
42    val target = UInt(VAddrBits.W)
43    val pred = UInt(2.W) // 2-bit saturated counter as a quick predictor
44  }
45
46  val btb = List.fill(BtbBanks)(List.fill(BtbWays)(
47    Module(new SRAMTemplate(btbEntry(), set = BtbSets / BtbBanks, shouldReset = true, holdRead = true, singlePort = true))))
48
49  // val fetchPkgAligned = btbAddr.getBank(io.in.pc.bits) === 0.U
50  val HeadBank = btbAddr.getBank(io.in.pc.bits)
51  val TailBank = btbAddr.getBank(io.in.pc.bits + FetchWidth.U << 2.U - 4.U)
52  for (b <- 0 until BtbBanks) {
53    for (w <- 0 until BtbWays) {
54      btb(b)(w).reset := reset.asBool
55      btb(b)(w).io.r.req.valid := io.in.pc.valid && Mux(TailBank > HeadBank, b.U >= HeadBank && b.U <= TailBank, b.U >= TailBank || b.U <= HeadBank)
56      btb(b)(w).io.r.req.bits.setIdx := btbAddr.getBankIdx(io.in.pc.bits)
57    }
58  }
59  // latch pc for 1 cycle latency when reading SRAM
60  val pcLatch = RegEnable(io.in.pc.bits, io.in.pc.valid)
61  val btbRead = Wire(Vec(BtbBanks, Vec(BtbWays, btbEntry())))
62  val btbHits = Wire(Vec(FetchWidth, Bool()))
63  val btbTargets = Wire(Vec(FetchWidth, UInt(VAddrBits.W)))
64  val btbTypes = Wire(Vec(FetchWidth, UInt(2.W)))
65  // val btbPreds = Wire(Vec(FetchWidth, UInt(2.W)))
66  val btbTakens = Wire(Vec(FetchWidth, Bool()))
67  for (b <- 0 until BtbBanks) {
68    for (w <- 0 until BtbWays) {
69      btbRead(b)(w) := btb(b)(w).io.r.resp.data(0)
70    }
71  }
72  for (i <- 0 until FetchWidth) {
73    btbHits(i) := false.B
74    for (b <- 0 until BtbBanks) {
75      when (b.U === btbAddr.getBank(pcLatch)) {
76        for (w <- 0 until BtbWays) {
77          when (btbRead(b)(w).valid && btbRead(b)(w).tag === btbAddr.getTag(Cat(pcLatch(VAddrBits - 1, 2), 0.U(2.W)) + i.U << 2)) {
78            btbHits(i) := !flush && RegNext(btb(b)(w).io.r.req.fire(), init = false.B)
79            btbTargets(i) := btbRead(b)(w).target
80            btbTypes(i) := btbRead(b)(w)._type
81            // btbPreds(i) := btbRead(b)(w).pred
82            btbTakens(i) := (btbRead(b)(w).pred)(1).asBool
83          }
84        }
85      }
86    }
87  }
88
89  // JBTAC, divided into 8 banks, makes prediction for indirect jump except ret.
90  val jbtacAddr = new TableAddr(log2Up(JbtacSize), JbtacBanks)
91  def jbtacEntry() = new Bundle {
92    val valid = Bool()
93    // TODO: don't need full length of tag and target
94    val tag = UInt(jbtacAddr.tagBits.W)
95    val target = UInt(VAddrBits.W)
96  }
97
98  val jbtac = List.fill(JbtacBanks)(Module(new SRAMTemplate(jbtacEntry(), set = JbtacSize / JbtacBanks, shouldReset = true, holdRead = true, singlePort = true)))
99
100  (0 until JbtacBanks).map(i => jbtac(i).reset := reset.asBool)
101  (0 until JbtacBanks).map(i => jbtac(i).io.r.req.valid := io.in.pc.valid)
102  (0 until JbtacBanks).map(i => jbtac(i).io.r.req.bits.setIdx := jbtacAddr.getBankIdx(Cat((io.in.pc.bits)(VAddrBits - 1, 2), 0.U(2.W)) + i.U << 2))
103
104  val jbtacRead = Wire(Vec(JbtacBanks, jbtacEntry()))
105  (0 until JbtacBanks).map(i => jbtacRead(i) := jbtac(i).io.r.resp.data(0))
106  val jbtacHits = Wire(Vec(FetchWidth, Bool()))
107  val jbtacTargets = Wire(Vec(FetchWidth, UInt(VAddrBits.W)))
108  val jbtacHeadBank = jbtacAddr.getBank(Cat(pcLatch(VAddrBits - 1, 2), 0.U(2.W)))
109  for (i <- 0 until FetchWidth) {
110    jbtacHits(i) := false.B
111    for (b <- 0 until JbtacBanks) {
112      when (jbtacHeadBank + i.U === b.U) {
113        jbtacHits(i) := jbtacRead(b).valid && jbtacRead(b).tag === jbtacAddr.getTag(Cat(pcLatch(VAddrBits - 1, 2), 0.U(2.W)) + i.U << 2) &&
114          !flush && RegNext(jbtac(b).io.r.req.fire(), init = false.B)
115        jbtacTargets(i) := jbtacRead(b).target
116      }
117    }
118  }
119
120  // redirect based on BTB and JBTAC
121  (0 until FetchWidth).map(i => io.predMask(i) := btbHits(i) && Mux(btbTypes(i) === BTBtype.B, btbTakens(i), true.B) || jbtacHits(i))
122  (0 until FetchWidth).map(i => io.predTargets(i) := Mux(btbHits(i) && !(btbTypes(i) === BTBtype.B && !btbTakens(i)), btbTargets(i), jbtacTargets(i)))
123
124
125  // update bpu, including BTB, JBTAC...
126  // 1. update BTB
127  // 1.1 read the selected bank
128  for (b <- 0 until BtbBanks) {
129    for (w <- 0 until BtbWays) {
130      btb(b)(w).io.r.req.valid := io.redirect.valid && btbAddr.getBank(io.redirect.bits.pc) === b.U
131      btb(b)(w).io.r.req.bits.setIdx := btbAddr.getBankIdx(io.redirect.bits.pc)
132    }
133  }
134
135  // 1.2 match redirect pc tag with the 4 tags in a btb line, find a way to write
136  val redirectLatch = RegEnable(io.redirect.bits, io.redirect.valid)
137  val bankLatch = btbAddr.getBank(redirectLatch.pc)
138  val btbUpdateRead = Wire(Vec(BtbWays, btbEntry()))
139  val btbValids = Wire(Vec(BtbWays, Bool()))
140  val btbUpdateTagHits = Wire(Vec(BtbWays, Bool()))
141  for (b <- 0 until BtbBanks) {
142    when (b.U === bankLatch) {
143      for (w <- 0 until BtbWays) {
144        btbUpdateRead(w) := btb(b)(w).io.r.resp.data(0)
145        btbValids(w) := btbUpdateRead(w).valid && RegNext(btb(b)(w).io.r.req.fire(), init = false.B)
146      }
147    }
148  }
149  (0 until BtbWays).map(w => btbUpdateTagHits(w) := btbValids(w) && btbUpdateRead(w).tag === btbAddr.getTag(redirectLatch.pc))
150  // val btbWriteWay = Wire(Vec(BtbWays, Bool()))
151  val btbWriteWay = Wire(UInt(BtbWays.W))
152  val btbInvalids = ~ btbValids.asUInt
153  when (btbUpdateTagHits.asUInt.orR) {
154    // tag hits
155    btbWriteWay := btbUpdateTagHits.asUInt
156  }.elsewhen (!btbValids.asUInt.andR) {
157    // no tag hits but there are free entries
158    btbWriteWay := Mux(btbInvalids >= 8.U, "b1000".U,
159      Mux(btbInvalids >= 4.U, "b0100".U,
160      Mux(btbInvalids >= 2.U, "b0010".U, "b0001".U)))
161  }.otherwise {
162    // no tag hits and no free entry, select a victim way
163    btbWriteWay := UIntToOH(LFSR64()(log2Up(BtbWays) - 1, 0))
164  }
165
166  // 1.3 calculate new 2-bit counter value
167  val btbWrite = WireInit(0.U.asTypeOf(btbEntry()))
168  btbWrite.valid := true.B
169  btbWrite.tag := btbAddr.getTag(redirectLatch.pc)
170  btbWrite._type := redirectLatch._type
171  btbWrite.target := redirectLatch.brTarget
172  val oldPred = PriorityMux(btbWriteWay.asTypeOf(Vec(BtbWays, Bool())), btbUpdateRead.map{ e => e.pred })
173  val newPred = Mux(redirectLatch.taken, Mux(oldPred === "b11".U, "b11".U, oldPred + 1.U),
174    Mux(oldPred === "b00".U, "b00".U, oldPred - 1.U))
175  btbWrite.pred := Mux(btbUpdateTagHits.asUInt.orR && redirectLatch._type === BTBtype.B, newPred, "b01".U)
176
177  // 1.4 write BTB
178  for (b <- 0 until BtbBanks) {
179    when (b.U === bankLatch) {
180      for (w <- 0 until BtbWays) {
181        btb(b)(w).io.w.req.valid := OHToUInt(btbWriteWay) === w.U &&
182          RegNext(io.redirect.valid, init = false.B) &&
183          (redirectLatch._type === BTBtype.B || redirectLatch._type === BTBtype.J)
184        btb(b)(w).io.w.req.bits.setIdx := btbAddr.getBankIdx(redirectLatch.pc)
185        btb(b)(w).io.w.req.bits.data := btbWrite
186      }
187    }
188  }
189
190  // 2. update JBTAC
191  val jbtacWrite = WireInit(0.U.asTypeOf(jbtacEntry()))
192  jbtacWrite.valid := true.B
193  jbtacWrite.tag := jbtacAddr.getTag(io.redirect.bits.pc)
194  jbtacWrite.target := io.redirect.bits.target
195  (0 until JbtacBanks).map(b =>
196    jbtac(b).io.w.req.valid := io.redirect.valid &&
197      b.U === jbtacAddr.getBank(io.redirect.bits.pc) &&
198      io.redirect.bits._type === BTBtype.I)
199  (0 until JbtacBanks).map(b => jbtac(b).io.w.req.bits.setIdx := jbtacAddr.getBankIdx(io.redirect.bits.pc))
200  (0 until JbtacBanks).map(b => jbtac(b).io.w.req.bits.data := jbtacWrite)
201}
202