Ariane處理器源碼剖析（二）：Frontend
本文介紹Ariane處理器的前端。由於前段最為重要的一個功能就是分支預測，因此本文會首先會回顧一下分支預測的基本概念，再進行代碼的分析。
先介紹一下與代碼無關的分支預測的基本概念，參考《超標量處理器設計》姚永斌。序號與原書序號相同，方便大傢查閱原書細節。
4 分支預測
4.1 概述
分支預測之所以能夠實現，是由分支指令的特性決定的，因為分支預測本質上是對分支指令的結果進行預測，而在一般的RISC指令集中，分支指令包含兩個要素。
- 方向，對於一個分支指令來說，它的方向隻可能有兩種，一種是發生跳轉（這稱為taken），另一種是不發生跳轉（稱為not taken）。
- 目標地址，目標地址在指令中可以有兩種存在形式。
- PC relative，也稱做直接跳轉（direct）。在指令中直接以立即數的形式給出一個相對於PC的偏移值（offset），當前分支指令的PC值（或者分支指令的下一條指令的PC值）加上這個偏移值就可以得到分支指令的目標地址。
- Absolute，也稱做間接跳轉（indirect）。分支指令的目標地址來自於一個通用寄存器的值，這個寄存器的編號由指令給出。由於寄存器的值是會經常變化的，因此這種類型的分支指令很難對目標地址進行預測，但是慶幸的是，程序當中大部分間接跳轉的分支指令都是用來調用子程序的Call/Return類型的指令，而這種類型的指令由於有著很強的規律性，是容易被預測的。
分支預測的最好時機就是在當前周期得到取指令地址的時候，在取指令的同時進行分支預測，這樣在下個周期就可以根據預測的結果繼續取指令。
在PC值剛剛產生的那個周期，根據這個PC值來預測本周期的指令組（fetch group）中是否存在分支指令，以及分支指令的方向和目標地址，這個過程如圖4.4所示。
4.2 分支指令的方向預測
對於分支指令來說，它的方向隻有兩個：發生跳轉（taken）和不發生跳轉（not taken），因此可以用1和0來表示。
4.2.1 基於兩位飽和計數器的分支預測
狀態機處於飽和狀態時，隻有兩次預測失敗才會改變預測的結果。
一般來講，都是使用Strongly not taken或者Weakly not taken作為初始狀態。
在圖4.10中，PHT（Pattern History Table）是一個表格，在其中存放著所有PC值所對應的兩位飽和計數器的值，例如圖4.10中使用PC值當中的k位來尋址PHT，因此PHT的大小就是2^k x 2bit。但是，這種方式來尋址PHT，就必然導致瞭k部分相同的所有PC值都使用同一個兩位飽和計數器的值，如果這些PC值對應的指令中不止有一條分支指令，那麼互相之間肯定會產生幹擾，這種情況稱為別名（aliasing）。
兩位的飽和計數器需要根據分支指令的結果（發生跳轉或者不發生跳轉）進行更新，有三個時間點可以對PHT進行更新。
- 在流水線的取指令階段，進行分支預測時，根據預測的結果來更新PHT；
- 在流水線的執行階段，當分支指令的方向被實際計算出來時，更新PHT；
- 在流水線的提交（Commit）階段，當分支指令要離開流水線時，更新PHT。
第（1）種方法對基於兩位飽和計數器的分支預測方法是不適用的，因為此時分支預測的結果可能是錯誤的，使用錯誤的結果來更新PHT是不可靠的。雖然第（2）種方法更新PHT的時間早於第（3）種方法，但是在超標量處理器中，如果對分支指令采用瞭亂序執行（out-of-order）的方式，那麼即使在執行階段得到瞭一條分支指令的結果，也不能夠保證這個結果是正確的，因為這條分支指令可能處於分支預測失敗（mis-prediction）的路徑上。所以隻有第（3）種方法，在分支指令被確認已經正確執行的時候，更新PHT才是萬無一失的。
4.2.2 基於局部歷史的分支預測
如果為每條分支指令都配一個BHR和PHT，這樣需要很大的存儲空間，將所有分支指令的BHR組合在一起稱為分支歷史寄存器表（Branch History Register Table，BHRT或BHT），在實際當中，BHT不可能照顧到每個PC，一般都是使用PC的一部分來尋址BHT，這就相當於一些PC會共用一個BHR，同時，PHT由於要占用大量的存儲空間，更需要被復用，可以采用如圖4.16所示的方法。
4eeb7b076593b5016c26dd596c9393e9
4.2.3 基於全局歷史的分支預測
基於全局歷史的分支預測方法，最理想的情況是對每條分支指令都使用一個PHT，這樣每條分支指令都會使用當前的GHR來尋址自身對應的PHT，這種預測方法的示意圖如圖4.20所示。
13121c2bcd31fc22ab5d5bcb9eb7f3a3
4.2.4 競爭的分支預測
4.2.5 分支預測的更新
1. 更新歷史寄存器
2. 更新飽和計數器
不管是在基於全局歷史的分支預測方法中，還是在基於局部歷史的分支預測方法中，都需要對PHT中的飽和計數器進行更新，當一條分支指令比較有規律時，它對應的飽和計數器總是處於飽和狀態，因此即使在分支指令退休的時候對PHT中的飽和計數器進行更新，也不會對分支預測的精度產生很大的負面影響，所以在這兩種分支預測方法中，一般都是在分支指令退休的時候對PHT中的飽和計數器進行更新。
4.3 分支指令的目標地址預測
在前面已經說過，分支指令的目標地址（target address）可以分為兩種，即直接跳轉（PC-relative）和間接跳轉（absolute）。對於直接跳轉的分支指令，由於它的偏移值（offset）是以立即數的形式固定在指令當中，所以它的目標地址也是固定的；而對於間接跳轉的分支指令來說，由於它的目標地址來自於通用寄存器，而通用寄存器的值是會經常變化的，所以對這種類型的分支指令來說，進行目標地址的預測並不是一件很容易的事情，但是慶幸的是，程序中大部分間接跳轉類型的分支指令是用來處理子程序調用的Call和Return指令，而這兩種指令的目標地址是有規律可循的，因此可以對其進行預測。
4.3.1 直接跳轉類型的分支預測
1. BTB
對於直接跳轉（PC-relative）類型的分支指令來說，它的目標地址有兩種情況。
- 不發生跳轉，目標地址 = 當前分支指令的PC值 + Sizeof（fetch group）。
- 發生跳轉，目標地址 = 當前分支指令的PC值 + Sign_extend（offset）。
由於分支預測是基於PC值進行的，不可能對每一個PC值都記錄下它的目標地址，所以一般都使用Cache的形式，使多個PC值共用一個空間來存儲目標地址，這個Cache稱為BTB（Branch Target Buffer），圖4.32表示瞭采用直接映射結構的BTB的示意圖。
2. BTB缺失的處理
方法一：停止執行
方法二：繼續執行
“better later than never“。
4.3.2 間接跳轉類型的分支預測
1. CALL/Return指令的分支預測
一條CALL指令對應的目標地址是固定的，因此可以使用BTB對CALL指令的目標地址進行預測，如圖4.38所示給出瞭一個例子。
但是對於一個子函數來說，例如printf函數，有很多地方都可以調用它，因此printf函數執行到最後一條Return指令的時候，返回的地方是會變化的。正因為Return指令的目標地址是不確定的，因此無法使用BTB對它的目標地址進行預測，但是可以看出，Return指令的目標地址總是等於最近一次執行的CALL指令的下一條指令的地址，如圖4.39所示。
根據Return指令的上述特點，可以設計一個存儲器，保存最近執行的CALL指令的下一條指令的地址，這個存儲器是後進先出的，稱之為RAS（Return Address Stack）。
2. 其他預測方法
4.3.3 小結
4.4 分支預測失敗時的恢復
在流水線的很多階段都可以對分支預測是否正確進行檢查。
- 在解碼階段。例如在這個階段發現瞭一條直接跳轉類型的無條件分支指令，則這條分支指令的方向和目標地址就可以得到瞭。例如一條目標地址位於寄存器中的間接跳轉指令，如果它在之前被預測為不發生跳轉，則此時在解碼階段就可以發現這個錯誤，但是在這個階段卻無法知道寄存器的內容，此時可以簡單地停止流水線，避免以後從流水線中抹掉指令而造成的功耗浪費。
- 在讀取物理寄存器的階段，如果此時讀取到瞭寄存器的值，那麼就可以對間接跳轉類型的分支指令所預測的目標地址進行檢查，如果發現目標地址預測錯誤瞭，那麼就可以使用正確的地址開始重新取指令，此時仍舊需要將分支指令之後進入到流水線的所有指令從流水線中抹掉。
- 在執行階段，不管是什麼類型的分支指令都可以被計算出結果，此時可以對分支預測是否正確進行檢查。
f018a981040da7fbe8fa184f34b911ea
需要對每一條分支指令都分配一個編號值，這樣才能在分支指令預測正確時，將屬於這個編號值的所有指令置為非推斷（non-speculative）的狀態，而在分支指令預測失敗時，抹掉流水線中所有處於分支預測失敗（mis-prediction）路徑上的指令。在解碼階段，對分支指令進行編號值的分配是最合適的，因為在這個階段可以確定地識別出哪些指令是分支指令。
4.5 超標量處理器的分支預測
到目前為止，本章所講述的分支預測都是對一條指令（也就是一個PC值）進行分之預測，對於普通的處理器（每周期隻取一條指令），這樣是沒有問題的，但是對於超標量處理器來說，在取指令時給出一個地址，會從I-Cache中取出多條指令，這些取出的指令組成瞭一個指令組（fetch group），處理器會自動根據指令組中指令的個數，調整取指令的地址，用來進行下個周期的取指令。
當然，如果對取指令的過程進行限制，例如對於一個4-way的超標量處理器來說，使每周期取出的指令位於四字對齊的邊界之內，那麼這樣就可以使用它們的公共地址（PC[31:4]）來尋址分支預測器，而對於分支預測器來說，它隻需要記錄下每組四字對齊的指令中，第一個預測跳轉的分支指令的信息就可以瞭。
在圖4.55中，當前周期取出的指令中是不包括分支指令的，所以不應該使用這條分支指令的預測信息，這需要在BTB中記錄下分支指令的偏移值。
圖4.56所示的這種對多條指令同時進行分支預測的方法，對分支指令的方向預測和目標地的預測是同時進行的，這樣可以保證盡快地得到分支預測的結果，但是在實際當中卻很難被接受，為什麼呢？這是由於對目標地址的預測來說，需要在一個周期內提供四個PC值對應的目標地址，這就相當於需要BTB支持四個讀端口，即使可以采用交疊（interleaving）的方式來避免真正的多端口，但是考慮到在使用過程中，最多隻會使用其中的一個端口的值，所以這種方式對於硬件的利用效率是很低的。
Frontend
PC gen流水級是負責產生next PC的。所有PC都是邏輯地址。如果邏輯地址到物理地址的映射改變瞭，那麼應該用一條sfence.vma指令來flush流水線和TLB（Translation Lookaside Buffer）。
模塊接口
typedef enum logic [2:0] {
NoCF, // No control flow prediction
Branch, // Branch
Jump, // Jump to address from immediate
JumpR, // Jump to address from registers
Return // Return Address Prediction
} cf_t;
// branch-predict
// this is the struct we get back from ex stage and we will use it to update
// all the necessary data structures
// bp_resolve_t
typedef struct packed {
logic valid; // prediction with all its values is valid
logic [riscv::VLEN-1:0] pc; // PC of predict or mis-predict
logic [riscv::VLEN-1:0] target_address; // target address at which to jump, or not
logic is_mispredict; // set if this was a mis-predict
logic is_taken; // branch is taken
cf_t cf_type; // Type of control flow change
} bp_resolve_t;
// branchpredict scoreboard entry
// this is the struct which we will inject into the pipeline to guide the various
// units towards the correct branch decision and resolve
typedef struct packed {
cf_t cf; // type of control flow prediction
logic [riscv::VLEN-1:0] predict_address; // target address at which to jump, or not
} branchpredict_sbe_t;
...
// ---------------
// IF/ID Stage
// ---------------
// store the decompressed instruction
typedef struct packed {
logic [riscv::VLEN-1:0] address; // the address of the instructions from below
logic [31:0] instruction; // instruction word
branchpredict_sbe_t branch_predict; // this field contains branch prediction information regarding the forward branch path
exception_t ex; // this field contains exceptions which might have happened earlier, e.g.: fetch exceptions
} fetch_entry_t;
相关推荐
關於CECS 03-2007《鉆芯法檢測混凝土強度技術規程》的“推定區間系數表”中給出的k1和k2系數應用註意事項
關於CECS 03-2007《鉆芯法檢測混凝土強度技術規程》的“推定區間系數表”中給出的k1和k2系數應用註意事項一、基礎概念：1、主控...
【iPhone12黑屏自救】解決黑屏重啟、黑屏開不瞭機故障！
iPhone12玩著遊戲，突然黑屏轉圈瞭？多次長按電源鍵重啟都不行？蘋果12刷著劇、看著小說莫名卡死，然後徹底黑屏瞭？一覺醒來...