xref: /XiangShan/src/main/scala/xiangshan/frontend/SC.scala (revision e69b7315c1440bd5420dd0c6c1b666bcc027525f) 
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}
30
31class SCReq(implicit p: Parameters) extends TageReq
32
33abstract class SCBundle(implicit p: Parameters) extends TageBundle with HasSCParameter {}
34abstract class SCModule(implicit p: Parameters) extends TageModule with HasSCParameter {}
35
36
37class SCMeta(val useSC: Boolean, val ntables: Int)(implicit p: Parameters) extends XSBundle with HasSCParameter {
38  val tageTaken = if (useSC) Bool() else UInt(0.W)
39  val scUsed = if (useSC) Bool() else UInt(0.W)
40  val scPred = if (useSC) Bool() else UInt(0.W)
41  // Suppose ctrbits of all tables are identical
42  val ctrs = if (useSC) Vec(ntables, SInt(SCCtrBits.W)) else Vec(ntables, SInt(0.W))
43}
44
45
46class SCResp(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
47  val ctr = Vec(2, SInt(ctrBits.W))
48}
49
50class SCUpdate(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
51  val pc = UInt(VAddrBits.W)
52  val folded_hist = new AllFoldedHistories(foldedGHistInfos)
53  val mask = Bool()
54  val oldCtr = SInt(ctrBits.W)
55  val tagePred = Bool()
56  val taken = Bool()
57}
58
59class SCTableIO(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
60  val req = Input(Valid(new SCReq))
61  val resp = Output(new SCResp(ctrBits))
62  val update = Input(new SCUpdate(ctrBits))
63}
64
65@chiselName
66class SCTable(val nRows: Int, val ctrBits: Int, val histLen: Int)(implicit p: Parameters)
67  extends SCModule with HasFoldedHistory {
68  val io = IO(new SCTableIO(ctrBits))
69
70  // val table = Module(new SRAMTemplate(SInt(ctrBits.W), set=nRows, way=2*TageBanks, shouldReset=true, holdRead=true, singlePort=false))
71  val table = Module(new SRAMTemplate(SInt(ctrBits.W), set=nRows, way=2, shouldReset=true, holdRead=true, singlePort=false))
72
73  val phistLen = PathHistoryLength
74  // def getIdx(hist: UInt, pc: UInt) = {
75  //   (compute_folded_ghist(hist, log2Ceil(nRows)) ^ (pc >> instOffsetBits))(log2Ceil(nRows)-1,0)
76  // }
77
78
79  val idxFhInfo = (histLen, min(log2Ceil(nRows), histLen))
80
81  def getFoldedHistoryInfo = Set(idxFhInfo).filter(_._1 > 0)
82
83  def getIdx(pc: UInt, allFh: AllFoldedHistories) = {
84    if (histLen > 0) {
85      val idx_fh = allFh.getHistWithInfo(idxFhInfo).folded_hist
86      // require(idx_fh.getWidth == log2Ceil(nRows))
87      ((pc >> instOffsetBits) ^ idx_fh)(log2Ceil(nRows)-1,0)
88    }
89    else {
90      pc(log2Ceil(nRows)-1,0)
91    }
92  }
93
94  def ctrUpdate(ctr: SInt, cond: Bool): SInt = signedSatUpdate(ctr, ctrBits, cond)
95
96  val s0_idx = getIdx(io.req.bits.pc, io.req.bits.folded_hist)
97  val s1_idx = RegEnable(s0_idx, enable=io.req.valid)
98
99  table.io.r.req.valid := io.req.valid
100  table.io.r.req.bits.setIdx := s0_idx
101
102  io.resp.ctr := table.io.r.resp.data
103
104  val update_wdata = Wire(SInt(ctrBits.W))
105  val updateWayMask =
106      VecInit((0 to 1).map(io.update.mask && _.U === io.update.tagePred.asUInt)).asUInt
107
108  val update_idx = getIdx(io.update.pc, io.update.folded_hist)
109
110  table.io.w.apply(
111    valid = io.update.mask,
112    data = VecInit(Seq.fill(2)(update_wdata)),
113    setIdx = update_idx,
114    waymask = updateWayMask
115  )
116
117  val wrBypassEntries = 4
118
119  class SCWrBypass extends XSModule {
120    val io = IO(new Bundle {
121      val wen = Input(Bool())
122      val update_idx  = Input(UInt(log2Ceil(nRows).W))
123      val update_ctrs  = Flipped(ValidIO(SInt(ctrBits.W)))
124      val update_ctrPos = Input(UInt(log2Ceil(2).W))
125      val update_altPos = Input(UInt(log2Ceil(2).W))
126
127      val hit   = Output(Bool())
128      val ctrs  = Vec(2, ValidIO(SInt(ctrBits.W)))
129    })
130
131    val idxes       = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, UInt(log2Ceil(nRows).W))))
132    val ctrs        = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2, SInt(ctrBits.W)))))
133    val ctr_valids  = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2, Bool()))))
134    val enq_idx     = RegInit(0.U(log2Ceil(wrBypassEntries).W))
135
136    val hits = VecInit((0 until wrBypassEntries).map { i => idxes(i) === io.update_idx })
137
138    val hit = hits.reduce(_||_)
139    val hit_idx = ParallelPriorityEncoder(hits)
140
141    io.hit := hit
142
143    for (i <- 0 until 2) {
144      io.ctrs(i).valid := ctr_valids(hit_idx)(i)
145      io.ctrs(i).bits := ctrs(hit_idx)(i)
146    }
147
148    when (io.wen) {
149      when (hit) {
150        ctrs(hit_idx)(io.update_ctrPos) := io.update_ctrs.bits
151        ctr_valids(hit_idx)(io.update_ctrPos) := io.update_ctrs.valid
152      }.otherwise {
153        ctr_valids(enq_idx)(io.update_altPos) := false.B
154        ctr_valids(enq_idx)(io.update_ctrPos) := io.update_ctrs.valid
155        ctrs(enq_idx)(io.update_ctrPos) := io.update_ctrs.bits
156      }
157    }
158
159    when(io.wen && !hit) {
160      idxes(enq_idx) := io.update_idx
161      enq_idx := (enq_idx + 1.U)(log2Ceil(wrBypassEntries)-1, 0)
162    }
163  }
164
165  val wrbypass = Module(new SCWrBypass)
166
167  val ctrPos = io.update.tagePred
168  val altPos = !io.update.tagePred
169  val bypass_ctr = wrbypass.io.ctrs(ctrPos)
170  val hit_and_valid = wrbypass.io.hit && bypass_ctr.valid
171  val oldCtr = Mux(hit_and_valid, bypass_ctr.bits, io.update.oldCtr)
172  update_wdata := ctrUpdate(oldCtr, io.update.taken)
173
174  wrbypass.io.wen := io.update.mask
175  wrbypass.io.update_ctrs.valid := io.update.mask
176  wrbypass.io.update_ctrs.bits := update_wdata
177  wrbypass.io.update_idx := update_idx
178  wrbypass.io.update_ctrPos := ctrPos
179  wrbypass.io.update_altPos := altPos
180
181  val u = io.update
182  XSDebug(io.req.valid,
183    p"scTableReq: pc=0x${Hexadecimal(io.req.bits.pc)}, " +
184    p"s0_idx=${s0_idx}\n")
185  XSDebug(RegNext(io.req.valid),
186    p"scTableResp: s1_idx=${s1_idx}," +
187    p"ctr:${io.resp.ctr}\n")
188  XSDebug(io.update.mask,
189    p"update Table: pc:${Hexadecimal(u.pc)}, " +
190    p"tageTaken:${u.tagePred}, taken:${u.taken}, oldCtr:${u.oldCtr}\n")
191  val updateCtrPos = io.update.tagePred
192  val hitCtr = wrbypass.io.ctrs(updateCtrPos).bits
193  XSDebug(wrbypass.io.hit && wrbypass.io.ctrs(updateCtrPos).valid && io.update.mask,
194    p"wrbypass hit idx:$update_idx, ctr:$hitCtr, " +
195    p"taken:${io.update.taken} newCtr:${update_wdata}\n")
196
197}
198
199class SCThreshold(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
200  val ctr = UInt(ctrBits.W)
201  def satPos(ctr: UInt = this.ctr) = ctr === ((1.U << ctrBits) - 1.U)
202  def satNeg(ctr: UInt = this.ctr) = ctr === 0.U
203  def neutralVal = (1.U << (ctrBits - 1))
204  val thres = UInt(8.W)
205  def initVal = 6.U
206  def minThres = 6.U
207  def maxThres = 31.U
208  def update(cause: Bool): SCThreshold = {
209    val res = Wire(new SCThreshold(this.ctrBits))
210    val newCtr = satUpdate(this.ctr, this.ctrBits, cause)
211    val newThres = Mux(res.satPos(newCtr) && this.thres <= maxThres, this.thres + 2.U,
212                      Mux(res.satNeg(newCtr) && this.thres >= minThres, this.thres - 2.U,
213                      this.thres))
214    res.thres := newThres
215    res.ctr := Mux(res.satPos(newCtr) || res.satNeg(newCtr), res.neutralVal, newCtr)
216    // XSDebug(true.B, p"scThres Update: cause${cause} newCtr ${newCtr} newThres ${newThres}\n")
217    res
218  }
219}
220
221object SCThreshold {
222  def apply(bits: Int)(implicit p: Parameters) = {
223    val t = Wire(new SCThreshold(ctrBits=bits))
224    t.ctr := t.neutralVal
225    t.thres := t.initVal
226    t
227  }
228}
229
230
231trait HasSC extends HasSCParameter { this: Tage =>
232  val update_on_mispred, update_on_unconf = WireInit(0.U.asTypeOf(Vec(TageBanks, Bool())))
233  var sc_fh_info = Set[FoldedHistoryInfo]()
234  if (EnableSC) {
235    val bank_scTables = BankSCTableInfos.zipWithIndex.map {
236      case (info, b) =>
237        val tables = info.map {
238          case (nRows, ctrBits, histLen) => {
239            val t = Module(new SCTable(nRows/TageBanks, ctrBits, histLen))
240            val req = t.io.req
241            req.valid := io.s0_fire
242            req.bits.pc := s0_pc
243            req.bits.folded_hist := io.in.bits.folded_hist
244            req.bits.phist := DontCare
245            if (!EnableSC) {t.io.update := DontCare}
246            t
247          }
248        }
249        tables
250    }
251    sc_fh_info = bank_scTables.flatMap(_.map(_.getFoldedHistoryInfo).reduce(_++_)).toSet
252
253    val scThresholds = List.fill(TageBanks)(RegInit(SCThreshold(5)))
254    val useThresholds = VecInit(scThresholds map (_.thres))
255    val updateThresholds = VecInit(useThresholds map (t => (t << 3) +& 21.U))
256
257    val s1_scResps = MixedVecInit(bank_scTables.map(b => VecInit(b.map(t => t.io.resp))))
258
259    val scUpdateMask = WireInit(0.U.asTypeOf(MixedVec(BankSCNTables.map(Vec(_, Bool())))))
260    val scUpdateTagePreds = Wire(Vec(TageBanks, Bool()))
261    val scUpdateTakens = Wire(Vec(TageBanks, Bool()))
262    val scUpdateOldCtrs = Wire(MixedVec(BankSCNTables.map(Vec(_, SInt(SCCtrBits.W)))))
263    scUpdateTagePreds := DontCare
264    scUpdateTakens := DontCare
265    scUpdateOldCtrs := DontCare
266
267    val updateSCMetas = VecInit(updateMetas.map(_.scMeta))
268
269    val s2_sc_used, s2_conf, s2_unconf, s2_agree, s2_disagree =
270      0.U.asTypeOf(Vec(TageBanks, Bool()))
271    val update_sc_used, update_conf, update_unconf, update_agree, update_disagree =
272      0.U.asTypeOf(Vec(TageBanks, Bool()))
273    val sc_misp_tage_corr, sc_corr_tage_misp =
274      0.U.asTypeOf(Vec(TageBanks, Bool()))
275
276    // for sc ctrs
277    def getCentered(ctr: SInt): SInt = (ctr << 1).asSInt + 1.S
278    // for tage ctrs
279    def getPvdrCentered(ctr: UInt): SInt = ((((ctr.zext -& 4.S) << 1).asSInt + 1.S) << 3).asSInt
280
281    for (w <- 0 until TageBanks) {
282      val scMeta = resp_meta(w).scMeta
283      scMeta := DontCare
284      // do summation in s2
285      val s1_scTableSums = VecInit(
286        (0 to 1) map { i =>
287          ParallelSingedExpandingAdd(s1_scResps(w) map (r => getCentered(r.ctr(i)))) // TODO: rewrite with wallace tree
288        }
289      )
290
291      val providerCtr = s1_providerCtrs(w)
292      val s1_pvdrCtrCentered = getPvdrCentered(providerCtr)
293      val s1_totalSums = VecInit(s1_scTableSums.map(_  +& s1_pvdrCtrCentered))
294      val s1_sumAbs = VecInit(s1_totalSums.map(_.abs.asUInt))
295      val s1_sumBelowThresholds = VecInit(s1_sumAbs map (_ <= useThresholds(w)))
296      val s1_scPreds = VecInit(s1_totalSums.map (_ >= 0.S))
297
298      val s2_sumBelowThresholds = RegEnable(s1_sumBelowThresholds, io.s1_fire)
299      val s2_scPreds = RegEnable(s1_scPreds, io.s1_fire)
300      val s2_sumAbs = RegEnable(s1_sumAbs, io.s1_fire)
301
302      val s2_scCtrs = RegEnable(VecInit(s1_scResps(w).map(r => r.ctr(s1_tageTakens(w).asUInt))), io.s1_fire)
303      val s2_chooseBit = s2_tageTakens(w)
304      scMeta.tageTaken := s2_tageTakens(w)
305      scMeta.scUsed := s2_provideds(w)
306      scMeta.scPred := s2_scPreds(s2_chooseBit)
307      scMeta.ctrs   := s2_scCtrs
308
309      when (s2_provideds(w)) {
310        s2_sc_used(w) := true.B
311        s2_unconf(w) := s2_sumBelowThresholds(s2_chooseBit)
312        s2_conf(w) := !s2_sumBelowThresholds(s2_chooseBit)
313        // Use prediction from Statistical Corrector
314        XSDebug(p"---------tage_bank_${w} provided so that sc used---------\n")
315        XSDebug(p"scCtrs:$s2_scCtrs, prdrCtr:${s2_providerCtrs(w)}, sumAbs:$s2_sumAbs, tageTaken:${s2_chooseBit}\n")
316        when (!s2_sumBelowThresholds(s2_chooseBit)) {
317          val pred = s2_scPreds(s2_chooseBit)
318          val debug_pc = Cat(debug_pc_s2, w.U, 0.U(instOffsetBits.W))
319          s2_agree(w) := s2_tageTakens(w) === pred
320          s2_disagree(w) := s2_tageTakens(w) =/= pred
321          // fit to always-taken condition
322          io.out.resp.s2.preds.br_taken_mask(w) := pred
323          XSDebug(p"pc(${Hexadecimal(debug_pc)}) SC(${w.U}) overriden pred to ${pred}\n")
324        }
325      }
326
327      val updateSCMeta = updateSCMetas(w)
328      val updateTageMeta = updateMetas(w)
329      when (updateValids(w) && updateSCMeta.scUsed.asBool) {
330        val scPred = updateSCMeta.scPred
331        val tagePred = updateSCMeta.tageTaken
332        val taken = update.preds.br_taken_mask(w)
333        val scOldCtrs = updateSCMeta.ctrs
334        val pvdrCtr = updateTageMeta.providerCtr
335        val sum = ParallelSingedExpandingAdd(scOldCtrs.map(getCentered)) +& getPvdrCentered(pvdrCtr)
336        val sumAbs = sum.abs.asUInt
337        scUpdateTagePreds(w) := tagePred
338        scUpdateTakens(w) := taken
339        (scUpdateOldCtrs(w) zip scOldCtrs).foreach{case (t, c) => t := c}
340
341        update_sc_used(w) := true.B
342        update_unconf(w) := sumAbs < useThresholds(w)
343        update_conf(w) := sumAbs >= useThresholds(w)
344        update_agree(w) := scPred === tagePred
345        update_disagree(w) := scPred =/= tagePred
346        sc_corr_tage_misp(w) := scPred === taken && tagePred =/= taken && update_conf(w)
347        sc_misp_tage_corr(w) := scPred =/= taken && tagePred === taken && update_conf(w)
348
349        val thres = useThresholds(w)
350        when (scPred =/= tagePred && sumAbs >= thres - 4.U && sumAbs <= thres - 2.U) {
351          val newThres = scThresholds(w).update(scPred =/= taken)
352          scThresholds(w) := newThres
353          XSDebug(p"scThres $w update: old ${useThresholds(w)} --> new ${newThres.thres}\n")
354        }
355
356        val updateThres = updateThresholds(w)
357        when (scPred =/= taken || sumAbs < updateThres) {
358          scUpdateMask(w).foreach(_ := true.B)
359          XSDebug(sum < 0.S,
360            p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
361            p"scSum(-$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateMisPreds(w)})\n"
362          )
363          XSDebug(sum >= 0.S,
364            p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
365            p"scSum(+$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateMisPreds(w)})\n"
366          )
367          XSDebug(p"bank(${w}), update: sc: ${updateSCMeta}\n")
368          update_on_mispred(w) := scPred =/= taken
369          update_on_unconf(w) := scPred === taken
370        }
371      }
372    }
373
374
375    for (b <- 0 until TageBanks) {
376      for (i <- 0 until BankSCNTables(b)) {
377        bank_scTables(b)(i).io.update.mask := RegNext(scUpdateMask(b)(i))
378        bank_scTables(b)(i).io.update.tagePred := RegNext(scUpdateTagePreds(b))
379        bank_scTables(b)(i).io.update.taken    := RegNext(scUpdateTakens(b))
380        bank_scTables(b)(i).io.update.oldCtr   := RegNext(scUpdateOldCtrs(b)(i))
381        bank_scTables(b)(i).io.update.pc := RegNext(update.pc)
382        bank_scTables(b)(i).io.update.folded_hist := RegNext(updateFHist)
383      }
384    }
385
386    tage_perf("sc_conf", PopCount(s2_conf), PopCount(update_conf))
387    tage_perf("sc_unconf", PopCount(s2_unconf), PopCount(update_unconf))
388    tage_perf("sc_agree", PopCount(s2_agree), PopCount(update_agree))
389    tage_perf("sc_disagree", PopCount(s2_disagree), PopCount(update_disagree))
390    tage_perf("sc_used", PopCount(s2_sc_used), PopCount(update_sc_used))
391    XSPerfAccumulate("sc_update_on_mispred", PopCount(update_on_mispred))
392    XSPerfAccumulate("sc_update_on_unconf", PopCount(update_on_unconf))
393    XSPerfAccumulate("sc_mispred_but_tage_correct", PopCount(sc_misp_tage_corr))
394    XSPerfAccumulate("sc_correct_and_tage_wrong", PopCount(sc_corr_tage_misp))
395
396  }
397
398  override def getFoldedHistoryInfo = Some(tage_fh_info ++ sc_fh_info)
399
400
401  val perfinfo = IO(new Bundle(){
402    val perfEvents = Output(new PerfEventsBundle(3))
403  })
404  val perfEvents = Seq(
405    ("tage_tht_hit                  ", updateMetas(1).provider.valid + updateMetas(0).provider.valid),
406    ("sc_update_on_mispred          ", PopCount(update_on_mispred) ),
407    ("sc_update_on_unconf           ", PopCount(update_on_unconf)  ),
408  )
409  for (((perf_out,(perf_name,perf)),i) <- perfinfo.perfEvents.perf_events.zip(perfEvents).zipWithIndex) {
410    perf_out.incr_step := RegNext(perf)
411  }
412}
413