xref: /XiangShan/src/main/scala/xiangshan/frontend/SC.scala (revision c6d439803a044ea209139672b25e35fe8d7f4aa0) 
1/***************************************************************************************
2* Copyright (c) 2020-2021 Institute of Computing Technology, Chinese Academy of Sciences
3*
4* XiangShan is licensed under Mulan PSL v2.
5* You can use this software according to the terms and conditions of the Mulan PSL v2.
6* You may obtain a copy of Mulan PSL v2 at:
7*          http://license.coscl.org.cn/MulanPSL2
8*
9* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
10* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
11* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
12*
13* See the Mulan PSL v2 for more details.
14***************************************************************************************/
15
16package xiangshan.frontend
17
18import chipsalliance.rocketchip.config.Parameters
19import chisel3._
20import chisel3.util._
21import xiangshan._
22import utils._
23import chisel3.experimental.chiselName
24
25import scala.math.min
26
27trait HasSCParameter extends HasTageParameter {
28  val SCHistLens = 0 :: TableInfo.map{ case (_,h,_) => h}.toList
29  val SCNTables = 6
30  val SCCtrBits = 6
31  val SCNRows = 1024
32  val SCTableInfo = Seq.fill(SCNTables)((SCNRows, SCCtrBits)) zip SCHistLens map {case ((n, cb), h) => (n, cb, h)}
33}
34
35class SCReq(implicit p: Parameters) extends TageReq
36
37abstract class SCBundle(implicit p: Parameters) extends TageBundle with HasSCParameter {}
38abstract class SCModule(implicit p: Parameters) extends TageModule with HasSCParameter {}
39
40class SCResp(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
41  val ctr = Vec(2, SInt(ctrBits.W))
42}
43
44class SCUpdate(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
45  val pc = UInt(VAddrBits.W)
46  val hist = UInt(HistoryLength.W)
47  val mask = Vec(TageBanks, Bool())
48  val oldCtrs = Vec(TageBanks, SInt(ctrBits.W))
49  val tagePreds = Vec(TageBanks, Bool())
50  val takens = Vec(TageBanks, Bool())
51}
52
53class SCTableIO(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
54  val req = Input(Valid(new SCReq))
55  val resp = Output(Vec(TageBanks, new SCResp(ctrBits)))
56  val update = Input(new SCUpdate(ctrBits))
57}
58
59@chiselName
60class SCTable(val nRows: Int, val ctrBits: Int, val histLen: Int)(implicit p: Parameters)
61  extends SCModule with HasFoldedHistory {
62  val io = IO(new SCTableIO(ctrBits))
63
64  val table = Module(new SRAMTemplate(SInt(ctrBits.W), set=nRows, way=2*TageBanks, shouldReset=true, holdRead=true, singlePort=false))
65
66  def getIdx(hist: UInt, pc: UInt) = {
67    (compute_folded_hist(hist, log2Ceil(nRows)) ^ (pc >> (instOffsetBits+log2Ceil(TageBanks))))(log2Ceil(nRows)-1,0)
68  }
69
70  def ctrUpdate(ctr: SInt, cond: Bool): SInt = signedSatUpdate(ctr, ctrBits, cond)
71
72  val if2_idx = getIdx(io.req.bits.hist, io.req.bits.pc)
73  val if3_idx = RegEnable(if2_idx, enable=io.req.valid)
74
75  val table_r =
76    VecInit((0 until TageBanks).map(b => VecInit((0 to 1).map(i => table.io.r.resp.data(b*2+i)))))
77
78
79  val if2_mask = io.req.bits.mask
80  val if3_mask = RegEnable(if2_mask, enable=io.req.valid)
81
82  val update_idx = getIdx(io.update.hist, io.update.pc)
83  val update_wdatas =
84    VecInit((0 until TageBanks).map(w =>
85      ctrUpdate(io.update.oldCtrs(w), io.update.takens(w))))
86
87  table.io.r.req.valid := io.req.valid
88  table.io.r.req.bits.setIdx := if2_idx
89
90  val updateWayMask =
91    VecInit((0 until TageBanks).map(b =>
92      VecInit((0 to 1).map(i =>
93        (io.update.mask(b) && i.U === io.update.tagePreds(b).asUInt))))).asUInt
94
95  table.io.w.apply(
96    valid = io.update.mask.asUInt.orR,
97    data = VecInit((0 until TageBanks*2).map(i => update_wdatas(i/2))),
98    setIdx = update_idx,
99    waymask = updateWayMask
100  )
101
102  (0 until TageBanks).map(b => {
103    io.resp(b).ctr := table_r(b)
104  })
105
106  val wrBypassEntries = 4
107
108  val wrbypass_idxs = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, UInt(log2Ceil(nRows).W))))
109  val wrbypass_ctrs = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2*TageBanks, SInt(ctrBits.W)))))
110  val wrbypass_ctr_valids = RegInit(0.U.asTypeOf(Vec(wrBypassEntries, Vec(2*TageBanks, Bool()))))
111  val wrbypass_enq_idx = RegInit(0.U(log2Ceil(wrBypassEntries).W))
112
113  when (reset.asBool) {
114    wrbypass_ctr_valids := 0.U.asTypeOf(Vec(wrBypassEntries, Vec(2*TageBanks, Bool())))
115  }
116
117  val wrbypass_hits = VecInit((0 until wrBypassEntries) map (i => wrbypass_idxs(i) === update_idx))
118  val wrbypass_hit = wrbypass_hits.asUInt.orR
119  val wrbypass_hit_idx = ParallelPriorityEncoder(wrbypass_hits)
120
121  for (w <- 0 until TageBanks) {
122    val ctrPos = (w << 1).U | io.update.tagePreds(w).asUInt
123    val altPos = (w << 1).U | ~io.update.tagePreds(w).asUInt
124    val bypass_ctr = wrbypass_ctrs(wrbypass_hit_idx)(ctrPos)
125    val hit_and_valid = wrbypass_hit && wrbypass_ctr_valids(wrbypass_hit_idx)(ctrPos)
126    val oldCtr = Mux(hit_and_valid, wrbypass_ctrs(wrbypass_hit_idx)(ctrPos), io.update.oldCtrs(w))
127    update_wdatas(w) := ctrUpdate(oldCtr, io.update.takens(w))
128
129    when (io.update.mask.reduce(_||_)) {
130      when (wrbypass_hit) {
131        when (io.update.mask(w)) {
132          wrbypass_ctrs(wrbypass_hit_idx)(ctrPos) := update_wdatas(w)
133          wrbypass_ctr_valids(wrbypass_hit_idx)(ctrPos) := true.B
134        }
135      }.otherwise {
136        // reset valid bit first
137        wrbypass_ctr_valids(wrbypass_enq_idx)(ctrPos) := false.B
138        wrbypass_ctr_valids(wrbypass_enq_idx)(altPos) := false.B
139        when (io.update.mask(w)) {
140          wrbypass_ctr_valids(wrbypass_enq_idx)(ctrPos) := true.B
141          wrbypass_ctrs(wrbypass_enq_idx)(w) := update_wdatas(w)
142        }
143      }
144    }
145  }
146
147  when (io.update.mask.reduce(_||_) && !wrbypass_hit) {
148    wrbypass_idxs(wrbypass_enq_idx) := update_idx
149    wrbypass_enq_idx := (wrbypass_enq_idx + 1.U)(log2Ceil(wrBypassEntries)-1,0)
150  }
151
152
153  if (BPUDebug && debug) {
154    val u = io.update
155    XSDebug(io.req.valid,
156      p"scTableReq: pc=0x${Hexadecimal(io.req.bits.pc)}, " +
157      p"if2_idx=${if2_idx}, hist=${Hexadecimal(io.req.bits.hist)}, " +
158      p"if2_mask=${Binary(if2_mask)}\n")
159    for (i <- 0 until TageBanks) {
160      XSDebug(RegNext(io.req.valid),
161        p"scTableResp[${i.U}]: if3_idx=${if3_idx}," +
162        p"ctr:${io.resp(i).ctr}, if3_mask=${Binary(if3_mask)}\n")
163      XSDebug(io.update.mask(i),
164        p"update Table: pc:${Hexadecimal(u.pc)}, hist:${Hexadecimal(u.hist)}, " +
165        p"bank:${i}, tageTaken:${u.tagePreds(i)}, taken:${u.takens(i)}, oldCtr:${u.oldCtrs(i)}\n")
166      val ctrPos = (i << 1).U | io.update.tagePreds(i).asUInt
167      val hitCtr = wrbypass_ctrs(wrbypass_hit_idx)(ctrPos)
168      XSDebug(wrbypass_hit && wrbypass_ctr_valids(wrbypass_hit_idx)(ctrPos) && io.update.mask(i),
169        p"bank $i wrbypass hit wridx:$wrbypass_hit_idx, idx:$update_idx, ctr:$hitCtr" +
170        p"taken:${io.update.takens(i)} newCtr:${update_wdatas(i)}\n")
171    }
172  }
173
174}
175
176class SCThreshold(val ctrBits: Int = 6)(implicit p: Parameters) extends SCBundle {
177  val ctr = UInt(ctrBits.W)
178  def satPos(ctr: UInt = this.ctr) = ctr === ((1.U << ctrBits) - 1.U)
179  def satNeg(ctr: UInt = this.ctr) = ctr === 0.U
180  def neutralVal = (1.U << (ctrBits - 1))
181  val thres = UInt(8.W)
182  def initVal = 6.U
183  def minThres = 6.U
184  def maxThres = 31.U
185  def update(cause: Bool): SCThreshold = {
186    val res = Wire(new SCThreshold(this.ctrBits))
187    val newCtr = satUpdate(this.ctr, this.ctrBits, cause)
188    val newThres = Mux(res.satPos(newCtr) && this.thres <= maxThres, this.thres + 2.U,
189                      Mux(res.satNeg(newCtr) && this.thres >= minThres, this.thres - 2.U,
190                      this.thres))
191    res.thres := newThres
192    res.ctr := Mux(res.satPos(newCtr) || res.satNeg(newCtr), res.neutralVal, newCtr)
193    // XSDebug(true.B, p"scThres Update: cause${cause} newCtr ${newCtr} newThres ${newThres}\n")
194    res
195  }
196}
197
198object SCThreshold {
199  def apply(bits: Int)(implicit p: Parameters) = {
200    val t = Wire(new SCThreshold(ctrBits=bits))
201    t.ctr := t.neutralVal
202    t.thres := t.initVal
203    t
204  }
205}
206
207
208trait HasSC extends HasSCParameter { this: Tage =>
209  val scTables = SCTableInfo.map {
210    case (nRows, ctrBits, histLen) => {
211      val t = Module(new SCTable(nRows/TageBanks, ctrBits, histLen))
212      val req = t.io.req
213      req.valid := io.pc.valid
214      req.bits.pc := io.pc.bits
215      req.bits.hist := io.hist
216      req.bits.mask := io.inMask
217      if (!EnableSC) {t.io.update := DontCare}
218      t
219    }
220  }
221
222  val scThresholds = List.fill(TageBanks)(RegInit(SCThreshold(5)))
223  val useThresholds = VecInit(scThresholds map (_.thres))
224  val updateThresholds = VecInit(useThresholds map (t => (t << 3) +& 21.U))
225
226  val if3_scResps = VecInit(scTables.map(t => t.io.resp))
227
228  val scUpdateMask = WireInit(0.U.asTypeOf(Vec(SCNTables, Vec(TageBanks, Bool()))))
229  val scUpdateTagePreds = Wire(Vec(TageBanks, Bool()))
230  val scUpdateTakens = Wire(Vec(TageBanks, Bool()))
231  val scUpdateOldCtrs = Wire(Vec(TageBanks, Vec(SCNTables, SInt(SCCtrBits.W))))
232  scUpdateTagePreds := DontCare
233  scUpdateTakens := DontCare
234  scUpdateOldCtrs := DontCare
235
236  val updateSCMetas = VecInit(u.metas.map(_.tageMeta.scMeta))
237
238  val if4_sc_used, if4_conf, if4_unconf, if4_agree, if4_disagree =
239    0.U.asTypeOf(Vec(TageBanks, Bool()))
240  val update_sc_used, update_conf, update_unconf, update_agree, update_disagree =
241    0.U.asTypeOf(Vec(TageBanks, Bool()))
242  val update_on_mispred, update_on_unconf, sc_misp_tage_corr, sc_corr_tage_misp =
243    0.U.asTypeOf(Vec(TageBanks, Bool()))
244
245  // for sc ctrs
246  def getCentered(ctr: SInt): SInt = (ctr << 1).asSInt + 1.S
247  // for tage ctrs
248  def getPvdrCentered(ctr: UInt): SInt = ((((ctr.zext -& 4.S) << 1).asSInt + 1.S) << 3).asSInt
249
250  for (w <- 0 until TageBanks) {
251    val scMeta = io.meta(w).scMeta
252    scMeta := DontCare
253    // do summation in if3
254    val if3_scTableSums = VecInit(
255      (0 to 1) map { i =>
256        ParallelSingedExpandingAdd(if3_scResps map (r => getCentered(r(w).ctr(i)))) // TODO: rewrite with wallace tree
257      }
258    )
259
260    val providerCtr = if3_providerCtrs(w)
261    val if3_pvdrCtrCentered = getPvdrCentered(providerCtr)
262    val if3_totalSums = VecInit(if3_scTableSums.map(_  +& if3_pvdrCtrCentered))
263    val if3_sumAbs = VecInit(if3_totalSums.map(_.abs.asUInt))
264    val if3_sumBelowThresholds = VecInit(if3_sumAbs map (_ <= useThresholds(w)))
265    val if3_scPreds = VecInit(if3_totalSums.map (_ >= 0.S))
266
267    val if4_sumBelowThresholds = RegEnable(if3_sumBelowThresholds, s3_fire)
268    val if4_scPreds = RegEnable(if3_scPreds, s3_fire)
269    val if4_sumAbs = RegEnable(if3_sumAbs, s3_fire)
270
271    val if4_scCtrs = RegEnable(VecInit(if3_scResps.map(r => r(w).ctr(if3_tageTakens(w).asUInt))), s3_fire)
272    val if4_chooseBit = if4_tageTakens(w)
273    scMeta.tageTaken := if4_tageTakens(w)
274    scMeta.scUsed := if4_provideds(w)
275    scMeta.scPred := if4_scPreds(if4_chooseBit)
276    scMeta.ctrs   := if4_scCtrs
277
278    when (if4_provideds(w)) {
279      if4_sc_used(w) := true.B
280      if4_unconf(w) := if4_sumBelowThresholds(if4_chooseBit)
281      if4_conf(w) := !if4_sumBelowThresholds(if4_chooseBit)
282      // Use prediction from Statistical Corrector
283      XSDebug(p"---------tage${w} provided so that sc used---------\n")
284      XSDebug(p"scCtrs:$if4_scCtrs, prdrCtr:${if4_providerCtrs(w)}, sumAbs:$if4_sumAbs, tageTaken:${if4_chooseBit}\n")
285      when (!if4_sumBelowThresholds(if4_chooseBit)) {
286        when (ctrl.sc_enable) {
287          val pred = if4_scPreds(if4_chooseBit)
288          val debug_pc = Cat(packetIdx(debug_pc_s3), w.U, 0.U(instOffsetBits.W))
289          XSDebug(p"pc(${Hexadecimal(debug_pc)}) SC(${w.U}) overriden pred to ${pred}\n")
290          if4_agree(w) := if4_tageTakens(w) === pred
291          if4_disagree(w) := if4_tageTakens(w) =/= pred
292          io.resp.takens(w) := pred
293        }
294      }
295    }
296
297    val updateSCMeta = updateSCMetas(w)
298    val updateTageMeta = updateMetas(w)
299    when (updateValids(w) && updateSCMeta.scUsed.asBool) {
300      val scPred = updateSCMeta.scPred
301      val tagePred = updateSCMeta.tageTaken
302      val taken = u.takens(w)
303      val scOldCtrs = updateSCMeta.ctrs
304      val pvdrCtr = updateTageMeta.providerCtr
305      val sum = ParallelSingedExpandingAdd(scOldCtrs.map(getCentered)) +& getPvdrCentered(pvdrCtr)
306      val sumAbs = sum.abs.asUInt
307      scUpdateTagePreds(w) := tagePred
308      scUpdateTakens(w) := taken
309      (scUpdateOldCtrs(w) zip scOldCtrs).foreach{case (t, c) => t := c}
310
311      update_sc_used(w) := true.B
312      update_unconf(w) := sumAbs < useThresholds(w)
313      update_conf(w) := sumAbs >= useThresholds(w)
314      update_agree(w) := scPred === tagePred
315      update_disagree(w) := scPred =/= tagePred
316      sc_corr_tage_misp(w) := scPred === taken && tagePred =/= taken && update_conf(w)
317      sc_misp_tage_corr(w) := scPred =/= taken && tagePred === taken && update_conf(w)
318
319      val thres = useThresholds(w)
320      when (scPred =/= tagePred && sumAbs >= thres - 4.U && sumAbs <= thres - 2.U) {
321        val newThres = scThresholds(w).update(scPred =/= taken)
322        scThresholds(w) := newThres
323        XSDebug(p"scThres $w update: old ${useThresholds(w)} --> new ${newThres.thres}\n")
324      }
325
326      val updateThres = updateThresholds(w)
327      when (scPred =/= taken || sumAbs < updateThres) {
328        scUpdateMask.foreach(t => t(w) := true.B)
329        XSDebug(sum < 0.S,
330        p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
331        p"scSum(-$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateTageMisPreds(w)})\n"
332        )
333        XSDebug(sum >= 0.S,
334        p"scUpdate: bank(${w}), scPred(${scPred}), tagePred(${tagePred}), " +
335        p"scSum(+$sumAbs), mispred: sc(${scPred =/= taken}), tage(${updateTageMisPreds(w)})\n"
336        )
337        XSDebug(p"bank(${w}), update: sc: ${updateSCMeta}\n")
338        update_on_mispred(w) := scPred =/= taken
339        update_on_unconf(w) := scPred === taken
340      }
341    }
342  }
343
344  tage_perf("sc_conf", PopCount(if4_conf), PopCount(update_conf))
345  tage_perf("sc_unconf", PopCount(if4_unconf), PopCount(update_unconf))
346  tage_perf("sc_agree", PopCount(if4_agree), PopCount(update_agree))
347  tage_perf("sc_disagree", PopCount(if4_disagree), PopCount(update_disagree))
348  tage_perf("sc_used", PopCount(if4_sc_used), PopCount(update_sc_used))
349  XSPerfAccumulate("sc_update_on_mispred", PopCount(update_on_mispred))
350  XSPerfAccumulate("sc_update_on_unconf", PopCount(update_on_unconf))
351  XSPerfAccumulate("sc_mispred_but_tage_correct", PopCount(sc_misp_tage_corr))
352  XSPerfAccumulate("sc_correct_and_tage_wrong", PopCount(sc_corr_tage_misp))
353
354  for (i <- 0 until SCNTables) {
355    scTables(i).io.update.mask := RegNext(scUpdateMask(i))
356    scTables(i).io.update.tagePreds := RegNext(scUpdateTagePreds)
357    scTables(i).io.update.takens    := RegNext(scUpdateTakens)
358    scTables(i).io.update.oldCtrs   := RegNext(VecInit(scUpdateOldCtrs.map(_(i))))
359    scTables(i).io.update.pc := RegNext(u.ftqPC)
360    scTables(i).io.update.hist := RegNext(updateHist)
361  }
362}
363