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+1isCall
: tailSlot中是否为call指令isRet
: tailSlot中是否为ret指令isJalr
: tailSlot中是否为间接跳转指令last_my_be_rvi_call
: 预测块最后可能是RVI callalways_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_jal
、is_jalr
、is_call
、is_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