FTB

概述

源代码:/xiangshan/frontend/FTB.scala

参数

FTB的基本参数如下所示:

 trait FTBParams extends HasXSParameter with HasBPUConst {
   val numEntries = FtbSize        // 2048
   val numWays    = FtbWays        // 4
   val numSets    = numEntries/numWays // 512
   val tagSize    = 20
 
   val TAR_STAT_SZ = 2
   def TAR_FIT = 0.U(TAR_STAT_SZ.W)
   def TAR_OVF = 1.U(TAR_STAT_SZ.W)
   def TAR_UDF = 2.U(TAR_STAT_SZ.W)
 
   def BR_OFFSET_LEN = 12
   def JMP_OFFSET_LEN = 20
 }

FTB整体的大小为2048个entry,即512个set,每个set为4-way。

FTB Entry

FTBEntry是FTB中存储的entry定义的数据结构:

 val valid       = Bool()
 // numBrSlot = 1, BR_OFFSET_LEN = 12
 val brSlots   = Vec(numBrSlot, new FtbSlot(BR_OFFSET_LEN))  // br偏移位宽为12位
 val tailSlot  = new FtbSlot(JMP_OFFSET_LEN, Some(BR_OFFSET_LEN)) // jump偏移位宽为20位
 // Partial Fall-Through Address
 val pftAddr     = UInt(log2Up(PredictWidth).W)
 val carry       = Bool()
 val isCall      = Bool()
 val isRet       = Bool()
 val isJalr      = Bool()
 val last_may_be_rvi_call = Bool()
 val always_taken = Vec(numBr, Bool())
  • valid: 当前entry是否有效
  • brSlots: 每个entry中记录的第一条条件分支(第二条在tailSlot中记录),FtbSlot的定义如下:
 class FtbSlot(val offsetLen: Int, val subOffsetLen: Option[Int] = None)(implicit p: Parameters) extends XSBundle with FTBParams {
   // PredictWidth = 16 (Enable C extendsion)
   // offset: 4-width
   val offset  = UInt(log2Ceil(PredictWidth).W)  // br指令基于start的偏移量
   val lower   = UInt(offsetLen.W)               // offsetLen 分支的偏移量位宽
   val tarStat = UInt(TAR_STAT_SZ.W)
   val sharing = Bool()                          // tailSlot是否用于记录br
   val valid   = Bool()
 }
  • tailSlot: 第二条分支指令(不一定是条件分支)
  • pftAddr: 顺序地址的低位部分(sequential)
  • carry: 计算顺序地址使用,若为1则需要将hipc+1
  • isCall: tailSlot中是否为call指令
  • isRet: tailSlot中是否为ret指令
  • isJalr: tailSlot中是否为间接跳转指令
  • last_my_be_rvi_call: 预测块最后可能是RVI call
  • always_taken: 总是跳转位,初始化时置1,第一次错误后置0

FTB Meta

FTB Meta用于记录一些杂项信息:

 class FTBMeta(implicit p: Parameters) extends XSBundle with FTBParams {
   val writeWay = UInt(log2Ceil(numWays).W)
   val hit = Bool()
   val pred_cycle = if (!env.FPGAPlatform) Some(UInt(64.W)) else None
 }

writeWay记录请求FTB时的地址命中的way,hit表示请求FTB的命中情况。

FTB Bank

IO

 val io = IO(new Bundle {
   val s1_fire = Input(Bool())
 
   // when ftb hit, read_hits.valid is true, and read_hits.bits is OH of hit way
   // when ftb not hit, read_hits.valid is false, and read_hits is OH of allocWay
   // val read_hits = Valid(Vec(numWays, Bool()))
   val req_pc = Flipped(DecoupledIO(UInt(VAddrBits.W)))
   val read_resp = Output(new FTBEntry)
   val read_hits = Valid(UInt(log2Ceil(numWays).W))
 
   val u_req_pc = Flipped(DecoupledIO(UInt(VAddrBits.W)))
   val update_hits = Valid(UInt(log2Ceil(numWays).W))
   val update_access = Input(Bool())
 
   val update_pc = Input(UInt(VAddrBits.W))
   val update_write_data = Flipped(Valid(new FTBEntryWithTag))
   val update_write_way = Input(UInt(log2Ceil(numWays).W))
   val update_write_alloc = Input(Bool())
 })

FTB的IO主要有两部分:用于读请求的req以及用于update的写入或者allocate。

需要注意的是,read_hits对于读请求时,若hit则表示命中的独热编码,若没有hit则表示allocate的位置1。

[1]  虽然注释是这么说明的,但从代码中并没有看出来

SRAM

 val ftb = Module(new SRAMTemplate(new FTBEntryWithTag, set = numSets, way = numWays, shouldReset = true, holdRead = false, singlePort = true))

FTBEntryWithTag实际上就是FTBEntry加上tag域:

 class FTBEntryWithTag(implicit p: Parameters) extends XSBundle with FTBParams with BPUUtils {
   val entry = new FTBEntry
   val tag = UInt(tagSize.W) // 20
 }

FTB Bank SRAM一共有512个set,每个set有4路,因此一共有2048个entry。

FTB Bank写(更新)的优先级要高于读:

 ftb.io.r.req.bits.setIdx := Mux(io.u_req_pc.valid, ftbAddr.getIdx(io.u_req_pc.bits), ftbAddr.getIdx(io.req_pc.bits))

从FTB中读取的entry,针对读或更新的tag进行比对,得到hit的独热编码(不会有multi hit):

 val total_hits = VecInit((0 until numWays).map(b => read_tags(b) === req_tag && read_entries(b).valid && io.s1_fire))
 val hit = total_hits.reduce(_||_)
 val hit_way = OHToUInt(total_hits)
 
 val u_total_hits = VecInit((0 until numWays).map(b =>
                                                  ftb.io.r.resp.data(b).tag === u_req_tag && ftb.io.r.resp.data(b).entry.valid && RegNext(io.update_access)))
 val u_hit = u_total_hits.reduce(_||_)
 val u_hit_way = OHToUInt(u_total_hits)

FTB的allocate算法使用PLRU。如果4个way都是valid的,则使用PLRU的state来选择替换哪个way,否则选择invalid的way数种最小的:

 def allocWay(valids: UInt, idx: UInt): UInt = {
   if (numWays > 1) {
     val w = Wire(UInt(log2Up(numWays).W))
     val valid = WireInit(valids.andR)
     w := Mux(valid, replacer.way(idx), PriorityEncoder(~valids))
     w
   } else {
     val w = WireInit(0.U(log2Up(numWays).W))
     w
   }
 }

更新FTB的逻辑稍微复杂一点。首先需要根据u_req_pc读取一次SRAM,看是否有hit的entry。如果需要allocate,则写入到allocate的way当中,如果不需要(update hit),则直接写入对应的hit way当中。

FTB Top

FTB的顶层module所使用的IO直接复用继承的BasePredictor IO定义,这涉及到整个BPU顶层逻辑,将在之后详细描述,在此先不展开。FTB top声明了FTB Bank的实例:

 val ftbBank = Module(new FTBBank(numSets, numWays))

Resp

只要s0_fire有效,就会不断的使用s0_pc请求FTB:

 ftbBank.io.req_pc.valid := io.s0_fire
 ftbBank.io.req_pc.bits := s0_pc

s0阶段的请求,数据需要在s1阶段才能得到,定义了s1、s2、s3阶段的hit以及resp信息,都为打拍后的结果:

 val ftb_entry = RegEnable(ftbBank.io.read_resp, io.s1_fire)
 val s3_ftb_entry = RegEnable(ftb_entry, io.s2_fire)
 val s1_hit = ftbBank.io.read_hits.valid && io.ctrl.btb_enable
 val s2_hit = RegEnable(s1_hit, io.s1_fire)
 val s3_hit = RegEnable(s2_hit, io.s2_fire)
 val writeWay = ftbBank.io.read_hits.bits

FTB resp在s2、s3阶段的输出即为打拍后的结果。其中ftb_entry即为s1阶段的resp打1拍后的结果:

 io.out.resp.s2.full_pred.hit       := s2_hit
 io.out.resp.s2.pc                  := s2_pc
 io.out.resp.s2.ftb_entry           := ftb_entry
 io.out.resp.s2.full_pred.fromFtbEntry(ftb_entry, s2_pc, Some((s1_pc, io.s1_fire)))
 io.out.resp.s2.is_minimal := false.B
 
 io.out.resp.s3.full_pred.hit := s3_hit
 io.out.resp.s3.pc                  := s3_pc
 io.out.resp.s3.ftb_entry           := s3_ftb_entry
 io.out.resp.s3.full_pred.fromFtbEntry(s3_ftb_entry, s3_pc, Some((s2_pc, io.s2_fire)))
 io.out.resp.s3.is_minimal := false.B

fromFtbEntry是用于将FTB中读取得到的ftb_entry中信息进行处理的工具函数,定义如下:

 def fromFtbEntry(entry: FTBEntry, pc: UInt, last_stage: Option[Tuple2[UInt, Bool]] = None) = {
   slot_valids := entry.brSlots.map(_.valid) :+ entry.tailSlot.valid
   targets := entry.getTargetVec(pc)
   jalr_target := targets.last
   offsets := entry.getOffsetVec
   is_jal := entry.tailSlot.valid && entry.isJal
   is_jalr := entry.tailSlot.valid && entry.isJalr
   is_call := entry.tailSlot.valid && entry.isCall
   is_ret := entry.tailSlot.valid && entry.isRet
   last_may_be_rvi_call := entry.last_may_be_rvi_call
   is_br_sharing := entry.tailSlot.valid && entry.tailSlot.sharing
 
   val startLower        = Cat(0.U(1.W),    pc(instOffsetBits+log2Ceil(PredictWidth)-1, instOffsetBits))
   val endLowerwithCarry = Cat(entry.carry, entry.pftAddr)
   fallThroughErr := startLower >= endLowerwithCarry
   fallThroughAddr := Mux(fallThroughErr, pc + (FetchWidth * 4).U, entry.getFallThrough(pc))
 }

实际上,在函数本体里并没有使用到last_stage信息,因此可以忽略。

slot_valid获取2个slot是否有效的信息。

getTargetVec用于获取当前entry中2个跳转slot的跳转目标地址,其分别调用2个slot中定义的getTarget函数:

 def getTargetVec(pc: UInt, last_stage: Option[Tuple2[UInt, Bool]] = None) = {
   VecInit((brSlots :+ tailSlot).map(_.getTarget(pc, last_stage)))
 }
 
 def getTarget(pc: UInt, last_stage: Option[Tuple2[UInt, Bool]] = None) = {
   def getTarget(offLen: Int)(pc: UInt, lower: UInt, stat: UInt,
                              last_stage: Option[Tuple2[UInt, Bool]] = None) = {
     val h = pc(VAddrBits-1, offLen+1)
     val higher = Wire(UInt((VAddrBits-offLen-1).W))
     val higher_plus_one = Wire(UInt((VAddrBits-offLen-1).W))
     val higher_minus_one = Wire(UInt((VAddrBits-offLen-1).W))
     if (last_stage.isDefined) {
       val last_stage_pc = last_stage.get._1
       val last_stage_pc_h = last_stage_pc(VAddrBits-1, offLen+1)
       val stage_en = last_stage.get._2
       higher := RegEnable(last_stage_pc_h, stage_en)
       higher_plus_one := RegEnable(last_stage_pc_h+1.U, stage_en)
       higher_minus_one := RegEnable(last_stage_pc_h-1.U, stage_en)
     } else {
       higher := h
       higher_plus_one := h + 1.U
       higher_minus_one := h - 1.U
     }
     val target =
     Cat(
       Mux1H(Seq(
         (stat === TAR_OVF, higher_plus_one),
         (stat === TAR_UDF, higher_minus_one),
         (stat === TAR_FIT, higher),
       )),
       lower(offLen-1, 0), 0.U(1.W)
     )
     require(target.getWidth == VAddrBits)
     require(offLen != 0)
     target
   }
   if (subOffsetLen.isDefined)
   Mux(sharing,
       getTarget(subOffsetLen.get)(pc, lower, tarStat, last_stage),
       getTarget(offsetLen)(pc, lower, tarStat, last_stage)
      )
   else
   getTarget(offsetLen)(pc, lower, tarStat, last_stage)
 }

该函数的主要作用其实就是判断跳转指令的高位部分是否需要+1或-1异或是保持,其通过stat中保存的状态来进行判断:

  • TAR_OVF(Target Overflow),则需要+1
  • TAR_UDF(Target Underflow),则需要-1
  • TAR_FIT(Target Fit),跳转目标仍然在偏移块内(br:4KB,jump:1MB),不变。

jalr_target只有可能是tailSlot,直接获取其目标地址。

offsets直接获取2个slot的offset域。

is_jalis_jalris_callis_ret分别判断tailSlot中的跳转指令类型,前面已经提到过,第一个slot一定是br,因此上述类型的指令只有可能存在第二个slot当中。

is_br_sharing表示tailSlot是否用于记录br指令。

fallThroughAddr为顺序执行的目标地址。

Update

FTB的更新逻辑较为复杂。首先,每次更新需要先检查更新数据结构中的FTB Meta信息,当中记录着需要更新的entry最初读FTB时的信息,包括hit的way、是否hit的信息。

val update_now = u_valid && u_meta.hit

如果当初读的时候就以及命中,则可以立刻进行更新,否则,则需要再读一次FTB,这是因为有可能在flying的途中,有其他相同地址的entry已经更新进去了。等待读取需要stall 2个周期。

  val update_need_read = u_valid && !u_meta.hit
  // stall one more cycle because we use a whole cycle to do update read tag hit
  io.s1_ready := ftbBank.io.req_pc.ready && !(update_need_read) && !RegNext(update_need_read)

  ftbBank.io.u_req_pc.valid := update_need_read
  ftbBank.io.u_req_pc.bits := update.pc

如果再次读命中,则用命中的信息来进行更新,否则,在FTB中为当前需要更新的entry进行allocate。

val ftb_write = Wire(new FTBEntryWithTag)
ftb_write.entry := Mux(update_now, update.ftb_entry, delay2_entry)
ftb_write.tag   := ftbAddr.getTag(Mux(update_now, update.pc, delay2_pc))(tagSize-1, 0)

val write_valid = update_now || DelayN(u_valid && !u_meta.hit, 2)

ftbBank.io.update_write_data.valid := write_valid
ftbBank.io.update_write_data.bits := ftb_write
ftbBank.io.update_pc          := Mux(update_now, update.pc,       delay2_pc)
ftbBank.io.update_write_way   := Mux(update_now, u_meta.writeWay, RegNext(ftbBank.io.update_hits.bits)) // use it one cycle later
ftbBank.io.update_write_alloc := Mux(update_now, false.B,         RegNext(!ftbBank.io.update_hits.valid)) // use it one cycle later
ftbBank.io.update_access := u_valid && !u_meta.hit
ftbBank.io.s1_fire := io.s1_fire

RISC-V CPU design engineer.