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