xref: /XiangShan/src/main/scala/xiangshan/frontend/SC.scala (revision 708ceed4afe43fb0ea3a52407e46b2794c573634) 
1/***************************************************************************************
2* Copyright (c) 2020-2021 Institute of Computing Technology, Chinese Academy of Sciences
3* Copyright (c) 2020-2021 Peng Cheng Laboratory
4*
5* XiangShan is licensed under Mulan PSL v2.
6* You can use this software according to the terms and conditions of the Mulan PSL v2.
7* You may obtain a copy of Mulan PSL v2 at:
8*          http://license.coscl.org.cn/MulanPSL2
9*
10* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
11* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
12* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
13*
14* See the Mulan PSL v2 for more details.
15***************************************************************************************/
16
17package xiangshan.frontend
18
19import chipsalliance.rocketchip.config.Parameters
20import chisel3._
21import chisel3.util._
22import xiangshan._
23import utils._
24import chisel3.experimental.chiselName
25
26import scala.math.min
27
28trait HasSCParameter extends TageParams {
29  val BankSCHistLens = BankTableInfos.map(info => 0 :: info.map{ case (_,h,_) => h}.toList)
30  val BankSCNTables = List(6, 6)
31  val SCCtrBits = 6
32  val SCNRows = 1024
33  val BankSCTableInfos = (BankSCNTables zip BankSCHistLens).map {
34    case (ntable, histlens) =>
35      Seq.fill(ntable)((SCNRows, SCCtrBits)) zip histlens map {case ((n, cb), h) => (n, cb, h)}
36  }
37}
38
39class SCReq(implicit p: Parameters) extends TageReq
40
41abstract class SCBundle(implicit p: Parameters) extends TageBundle with HasSCParameter {}
42abstract class SCModule(implicit p: Parameters) extends TageModule with HasSCParameter {}
43
44
45class SCMeta(val useSC: Boolean, val ntables: Int)(implicit p: Parameters) extends XSBundle with HasSCParameter {
46  val tageTaken = if (useSC) Bool() else UInt(0.W)
47  val scUsed = if (useSC) Bool() else UInt(0.W)
48  val scPred = if (useSC) Bool() else UInt(0.W)
49  // Suppose ctrbits of all tables are identical
50  val ctrs = if (useSC) Vec(ntables, SInt(SCCtrBits.W)) else Vec(ntables, SInt(0.W))
51}
52
53
54class SCResp(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
55  val ctr = Vec(2, SInt(ctrBits.W))
56}
57
58class SCUpdate(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
59  val pc = UInt(VAddrBits.W)
60  val hist = UInt(HistoryLength.W)
61  val mask = Bool()
62  val oldCtr = SInt(ctrBits.W)
63  val tagePred = Bool()
64  val taken = Bool()
65}
66
67class SCTableIO(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
68  val req = Input(Valid(new SCReq))
69  val resp = Output(new SCResp(ctrBits))
70  val update = Input(new SCUpdate(ctrBits))
71}
72
73@chiselName
74class SCTable(val nRows: Int, val ctrBits: Int, val histLen: Int)(implicit p: Parameters)
75  extends SCModule with HasFoldedHistory {
76  val io = IO(new SCTableIO(ctrBits))
77
78  // val table = Module(new SRAMTemplate(SInt(ctrBits.W), set=nRows, way=2*TageBanks, shouldReset=true, holdRead=true, singlePort=false))
79  val table = Module(new SRAMTemplate(SInt(ctrBits.W), set=nRows, way=2, shouldReset=true, holdRead=true, singlePort=false))
80
81  val phistLen = PathHistoryLength
82  def getIdx(hist: UInt, pc: UInt) = {
83    (compute_folded_ghist(hist, log2Ceil(nRows)) ^ (pc >> instOffsetBits))(log2Ceil(nRows)-1,0)
84  }
85
86  def ctrUpdate(ctr: SInt, cond: Bool): SInt = signedSatUpdate(ctr, ctrBits, cond)
87
88  val s0_idx = getIdx(io.req.bits.hist, io.req.bits.pc)
89  val s1_idx = RegEnable(s0_idx, enable=io.req.valid)
90
91  table.io.r.req.valid := io.req.valid
92  table.io.r.req.bits.setIdx := s0_idx
93
94  io.resp.ctr := table.io.r.resp.data
95
96  val update_wdata = Wire(SInt(ctrBits.W))
97  val updateWayMask =
98      VecInit((0 to 1).map(io.update.mask && _.U === io.update.tagePred.asUInt)).asUInt
99
100  val update_idx = getIdx(io.update.hist, io.update.pc)
101
102  table.io.w.apply(
103    valid = io.update.mask,
104    data = VecInit(Seq.fill(2)(update_wdata)),
105    setIdx = update_idx,
106    waymask = updateWayMask
107  )
108
109  val wrBypassEntries = 4
110
111  class SCWrBypass extends XSModule {
112    val io = IO(new Bundle {
113      val wen = Input(Bool())
114      val update_idx  = Input(UInt(log2Ceil(nRows).W))
115      val update_ctrs  = Flipped(ValidIO(SInt(ctrBits.W)))
116      val update_ctrPos = Input(UInt(log2Ceil(2).W))
117      val update_altPos = Input(UInt(log2Ceil(2).W))
118
119      val hit   = Output(Bool())
120      val ctrs  = Vec(2, ValidIO(SInt(ctrBits.W)))
121    })
122
123    val idxes       = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, UInt(log2Ceil(nRows).W))))
124    val ctrs        = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2, SInt(ctrBits.W)))))
125    val ctr_valids  = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2, Bool()))))
126    val enq_idx     = RegInit(0.U(log2Ceil(wrBypassEntries).W))
127
128    val hits = VecInit((0 until wrBypassEntries).map { i => idxes(i) === io.update_idx })
129
130    val hit = hits.reduce(_||_)
131    val hit_idx = ParallelPriorityEncoder(hits)
132
133    io.hit := hit
134
135    for (i <- 0 until 2) {
136      io.ctrs(i).valid := ctr_valids(hit_idx)(i)
137      io.ctrs(i).bits := ctrs(hit_idx)(i)
138    }
139
140    when (io.wen) {
141      when (hit) {
142        ctrs(hit_idx)(io.update_ctrPos) := io.update_ctrs.bits
143        ctr_valids(hit_idx)(io.update_ctrPos) := io.update_ctrs.valid
144      }.otherwise {
145        ctr_valids(enq_idx)(io.update_altPos) := false.B
146        ctr_valids(enq_idx)(io.update_ctrPos) := io.update_ctrs.valid
147        ctrs(enq_idx)(io.update_ctrPos) := io.update_ctrs.bits
148      }
149    }
150
151    when(io.wen && !hit) {
152      idxes(enq_idx) := io.update_idx
153      enq_idx := (enq_idx + 1.U)(log2Ceil(wrBypassEntries)-1, 0)
154    }
155  }
156
157  val wrbypass = Module(new SCWrBypass)
158
159  val ctrPos = io.update.tagePred
160  val altPos = !io.update.tagePred
161  val bypass_ctr = wrbypass.io.ctrs(ctrPos)
162  val hit_and_valid = wrbypass.io.hit && bypass_ctr.valid
163  val oldCtr = Mux(hit_and_valid, bypass_ctr.bits, io.update.oldCtr)
164  update_wdata := ctrUpdate(oldCtr, io.update.taken)
165
166  wrbypass.io.wen := io.update.mask
167  wrbypass.io.update_ctrs.valid := io.update.mask
168  wrbypass.io.update_ctrs.bits := update_wdata
169  wrbypass.io.update_idx := update_idx
170  wrbypass.io.update_ctrPos := ctrPos
171  wrbypass.io.update_altPos := altPos
172
173  if (BPUDebug && debug) {
174    val u = io.update
175    XSDebug(io.req.valid,
176      p"scTableReq: pc=0x${Hexadecimal(io.req.bits.pc)}, " +
177      p"s0_idx=${s0_idx}, hist=${Hexadecimal(io.req.bits.hist)}\n")
178    XSDebug(RegNext(io.req.valid),
179      p"scTableResp: s1_idx=${s1_idx}," +
180      p"ctr:${io.resp.ctr}\n")
181    XSDebug(io.update.mask,
182      p"update Table: pc:${Hexadecimal(u.pc)}, hist:${Hexadecimal(u.hist)}, " +
183      p"tageTaken:${u.tagePred}, taken:${u.taken}, oldCtr:${u.oldCtr}\n")
184    val ctrPos = io.update.tagePred
185    val hitCtr = wrbypass.io.ctrs(ctrPos).bits
186    XSDebug(wrbypass.io.hit && wrbypass.io.ctrs(ctrPos).valid && io.update.mask,
187      p"wrbypass hit idx:$update_idx, ctr:$hitCtr, " +
188      p"taken:${io.update.taken} newCtr:${update_wdata}\n")
189  }
190
191}
192
193class SCThreshold(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
194  val ctr = UInt(ctrBits.W)
195  def satPos(ctr: UInt = this.ctr) = ctr === ((1.U << ctrBits) - 1.U)
196  def satNeg(ctr: UInt = this.ctr) = ctr === 0.U
197  def neutralVal = (1.U << (ctrBits - 1))
198  val thres = UInt(8.W)
199  def initVal = 6.U
200  def minThres = 6.U
201  def maxThres = 31.U
202  def update(cause: Bool): SCThreshold = {
203    val res = Wire(new SCThreshold(this.ctrBits))
204    val newCtr = satUpdate(this.ctr, this.ctrBits, cause)
205    val newThres = Mux(res.satPos(newCtr) && this.thres <= maxThres, this.thres + 2.U,
206                      Mux(res.satNeg(newCtr) && this.thres >= minThres, this.thres - 2.U,
207                      this.thres))
208    res.thres := newThres
209    res.ctr := Mux(res.satPos(newCtr) || res.satNeg(newCtr), res.neutralVal, newCtr)
210    // XSDebug(true.B, p"scThres Update: cause${cause} newCtr ${newCtr} newThres ${newThres}\n")
211    res
212  }
213}
214
215object SCThreshold {
216  def apply(bits: Int)(implicit p: Parameters) = {
217    val t = Wire(new SCThreshold(ctrBits=bits))
218    t.ctr := t.neutralVal
219    t.thres := t.initVal
220    t
221  }
222}
223
224
225trait HasSC extends HasSCParameter { this: Tage =>
226
227  val bank_scTables = BankSCTableInfos.zipWithIndex.map {
228    case (info, b) =>
229      val tables = info.map {
230        case (nRows, ctrBits, histLen) => {
231          val t = Module(new SCTable(nRows/TageBanks, ctrBits, histLen))
232          val req = t.io.req
233          req.valid := io.s0_fire
234          req.bits.pc := s0_pc
235          req.bits.hist := io.in.bits.ghist << b
236          req.bits.phist := DontCare
237          if (!EnableSC) {t.io.update := DontCare}
238          t
239        }
240      }
241      tables
242  }
243
244  val scThresholds = List.fill(TageBanks)(RegInit(SCThreshold(5)))
245  val useThresholds = VecInit(scThresholds map (_.thres))
246  val updateThresholds = VecInit(useThresholds map (t => (t << 3) +& 21.U))
247
248  val s1_scResps = MixedVecInit(bank_scTables.map(b => VecInit(b.map(t => t.io.resp))))
249
250  val scUpdateMask = WireInit(0.U.asTypeOf(MixedVec(BankSCNTables.map(Vec(_, Bool())))))
251  val scUpdateTagePreds = Wire(Vec(TageBanks, Bool()))
252  val scUpdateTakens = Wire(Vec(TageBanks, Bool()))
253  val scUpdateOldCtrs = Wire(MixedVec(BankSCNTables.map(Vec(_, SInt(SCCtrBits.W)))))
254  scUpdateTagePreds := DontCare
255  scUpdateTakens := DontCare
256  scUpdateOldCtrs := DontCare
257
258  val updateSCMetas = VecInit(updateMetas.map(_.scMeta))
259
260  val s2_sc_used, s2_conf, s2_unconf, s2_agree, s2_disagree =
261    0.U.asTypeOf(Vec(TageBanks, Bool()))
262  val update_sc_used, update_conf, update_unconf, update_agree, update_disagree =
263    0.U.asTypeOf(Vec(TageBanks, Bool()))
264  val update_on_mispred, update_on_unconf, sc_misp_tage_corr, sc_corr_tage_misp =
265    0.U.asTypeOf(Vec(TageBanks, Bool()))
266
267  // for sc ctrs
268  def getCentered(ctr: SInt): SInt = (ctr << 1).asSInt + 1.S
269  // for tage ctrs
270  def getPvdrCentered(ctr: UInt): SInt = ((((ctr.zext -& 4.S) << 1).asSInt + 1.S) << 3).asSInt
271
272  for (w <- 0 until TageBanks) {
273    val scMeta = resp_meta(w).scMeta
274    scMeta := DontCare
275    // do summation in s2
276    val s1_scTableSums = VecInit(
277      (0 to 1) map { i =>
278        ParallelSingedExpandingAdd(s1_scResps(w) map (r => getCentered(r.ctr(i)))) // TODO: rewrite with wallace tree
279      }
280    )
281
282    val providerCtr = s1_providerCtrs(w)
283    val s1_pvdrCtrCentered = getPvdrCentered(providerCtr)
284    val s1_totalSums = VecInit(s1_scTableSums.map(_  +& s1_pvdrCtrCentered))
285    val s1_sumAbs = VecInit(s1_totalSums.map(_.abs.asUInt))
286    val s1_sumBelowThresholds = VecInit(s1_sumAbs map (_ <= useThresholds(w)))
287    val s1_scPreds = VecInit(s1_totalSums.map (_ >= 0.S))
288
289    val s2_sumBelowThresholds = RegEnable(s1_sumBelowThresholds, io.s1_fire)
290    val s2_scPreds = RegEnable(s1_scPreds, io.s1_fire)
291    val s2_sumAbs = RegEnable(s1_sumAbs, io.s1_fire)
292
293    val s2_scCtrs = RegEnable(VecInit(s1_scResps(w).map(r => r.ctr(s1_tageTakens(w).asUInt))), io.s1_fire)
294    val s2_chooseBit = s2_tageTakens(w)
295    scMeta.tageTaken := s2_tageTakens(w)
296    scMeta.scUsed := s2_provideds(w)
297    scMeta.scPred := s2_scPreds(s2_chooseBit)
298    scMeta.ctrs   := s2_scCtrs
299
300    when (s2_provideds(w)) {
301      s2_sc_used(w) := true.B
302      s2_unconf(w) := s2_sumBelowThresholds(s2_chooseBit)
303      s2_conf(w) := !s2_sumBelowThresholds(s2_chooseBit)
304      // Use prediction from Statistical Corrector
305      XSDebug(p"---------tage_bank_${w} provided so that sc used---------\n")
306      XSDebug(p"scCtrs:$s2_scCtrs, prdrCtr:${s2_providerCtrs(w)}, sumAbs:$s2_sumAbs, tageTaken:${s2_chooseBit}\n")
307      when (!s2_sumBelowThresholds(s2_chooseBit)) {
308        val pred = s2_scPreds(s2_chooseBit)
309        val debug_pc = Cat(debug_pc_s2, w.U, 0.U(instOffsetBits.W))
310        s2_agree(w) := s2_tageTakens(w) === pred
311        s2_disagree(w) := s2_tageTakens(w) =/= pred
312        // fit to always-taken condition
313        io.out.resp.s2.preds.taken_mask(w) := pred
314        XSDebug(p"pc(${Hexadecimal(debug_pc)}) SC(${w.U}) overriden pred to ${pred}\n")
315      }
316    }
317
318    val updateSCMeta = updateSCMetas(w)
319    val updateTageMeta = updateMetas(w)
320    when (updateValids(w) && updateSCMeta.scUsed.asBool) {
321      val scPred = updateSCMeta.scPred
322      val tagePred = updateSCMeta.tageTaken
323      val taken = update.preds.taken_mask(w)
324      val scOldCtrs = updateSCMeta.ctrs
325      val pvdrCtr = updateTageMeta.providerCtr
326      val sum = ParallelSingedExpandingAdd(scOldCtrs.map(getCentered)) +& getPvdrCentered(pvdrCtr)
327      val sumAbs = sum.abs.asUInt
328      scUpdateTagePreds(w) := tagePred
329      scUpdateTakens(w) := taken
330      (scUpdateOldCtrs(w) zip scOldCtrs).foreach{case (t, c) => t := c}
331
332      update_sc_used(w) := true.B
333      update_unconf(w) := sumAbs < useThresholds(w)
334      update_conf(w) := sumAbs >= useThresholds(w)
335      update_agree(w) := scPred === tagePred
336      update_disagree(w) := scPred =/= tagePred
337      sc_corr_tage_misp(w) := scPred === taken && tagePred =/= taken && update_conf(w)
338      sc_misp_tage_corr(w) := scPred =/= taken && tagePred === taken && update_conf(w)
339
340      val thres = useThresholds(w)
341      when (scPred =/= tagePred && sumAbs >= thres - 4.U && sumAbs <= thres - 2.U) {
342        val newThres = scThresholds(w).update(scPred =/= taken)
343        scThresholds(w) := newThres
344        XSDebug(p"scThres $w update: old ${useThresholds(w)} --> new ${newThres.thres}\n")
345      }
346
347      val updateThres = updateThresholds(w)
348      when (scPred =/= taken || sumAbs < updateThres) {
349        scUpdateMask(w).foreach(_ := true.B)
350        XSDebug(sum < 0.S,
351          p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
352          p"scSum(-$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateMisPreds(w)})\n"
353        )
354        XSDebug(sum >= 0.S,
355          p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
356          p"scSum(+$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateMisPreds(w)})\n"
357        )
358        XSDebug(p"bank(${w}), update: sc: ${updateSCMeta}\n")
359        update_on_mispred(w) := scPred =/= taken
360        update_on_unconf(w) := scPred === taken
361      }
362    }
363  }
364
365
366  for (b <- 0 until TageBanks) {
367    for (i <- 0 until BankSCNTables(b)) {
368      bank_scTables(b)(i).io.update.mask := RegNext(scUpdateMask(b)(i))
369      bank_scTables(b)(i).io.update.tagePred := RegNext(scUpdateTagePreds(b))
370      bank_scTables(b)(i).io.update.taken    := RegNext(scUpdateTakens(b))
371      bank_scTables(b)(i).io.update.oldCtr   := RegNext(scUpdateOldCtrs(b)(i))
372      bank_scTables(b)(i).io.update.pc := RegNext(update.pc)
373      bank_scTables(b)(i).io.update.hist := RegNext(updateHist.predHist << b)
374    }
375  }
376
377  tage_perf("sc_conf", PopCount(s2_conf), PopCount(update_conf))
378  tage_perf("sc_unconf", PopCount(s2_unconf), PopCount(update_unconf))
379  tage_perf("sc_agree", PopCount(s2_agree), PopCount(update_agree))
380  tage_perf("sc_disagree", PopCount(s2_disagree), PopCount(update_disagree))
381  tage_perf("sc_used", PopCount(s2_sc_used), PopCount(update_sc_used))
382  XSPerfAccumulate("sc_update_on_mispred", PopCount(update_on_mispred))
383  XSPerfAccumulate("sc_update_on_unconf", PopCount(update_on_unconf))
384  XSPerfAccumulate("sc_mispred_but_tage_correct", PopCount(sc_misp_tage_corr))
385  XSPerfAccumulate("sc_correct_and_tage_wrong", PopCount(sc_corr_tage_misp))
386}
387