TWI223195B - Optimized branch predictions for strongly predicted compiler branches - Google Patents

Description

1223195

、發明說明（ 經濟部智慧財產局員工消费合作社印製 为支目標位址上的指令。因爲微處理器還不知道該預測正 崔與否，所以该分支預測之後執行的指令都是以預測式的 。因此，可能尚未完全完成該等預測式指令所要執行的任 何作業。例如，如果以預測方式執行一記憶體寫入作業， 則在成功地執行所有先前的分支條件之前，不得將該窝入 作業傳送到一圮憶體系統。否則，一錯誤預測的路徑中之 才曰令可能不正確地改變了記憶體的内容。 如果最後決定該分支預測是正確的，則使該等以預測方 式執行的指令退休，或以其他方式提供該等指令。在一記 憶體窝入的例子中，係將該寫入作業傳送到記憶體系統， 而執行指令的退休。如果最後發現該分支預測是錯誤的， 貝J通^自系統中清除在該錯誤預測的路徑之後的任何以預 測方式執行的指令。在該記憶體窝入例子中，並不將該寫 入作業傳送到1己憶體系統，而是捨棄該寫入作業。 爲了要加速分支預測，某些現階段最高技術的微處理器 包含一分支預測表（Branch Prediction Table ;簡稱BPT)，用 以提供最近預測的各分支之快取記憶體、以及諸如亦被稱 爲動怨過去記錄的先前執行之過去記綠之對應的預測資訊 、及（或）對分支的預設及預測之成功與否。 除了動態分支過去記錄之外，預測機制亦可利用編譯器 提示來協助分支預測。通常係利用藉由執行一個具有數個 資料集的程式而取得之程式特徵檔案，而決定編譯器提示 。利用找出一編譯器的特徵樓案之方式，可得知是否採取 一分支的可能性、以及採取該該分支的確定性。可將該資 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ------------- 裝 i !i — ——訂 _ — — — ！ — -^ (請先閱讀背面之注意事項再填寫本頁) 1223195 A7

經濟部智慧財產局員工消費合作社印製 五、發明說明（3 ) 訊編碼成一指令。然而，爲了要自指令中找出該資訊，需 要自指令快取記憶體讀取該指令，並將該指令解碼。其問 題在於：係在指令管線的後段才將指令解碼。因此，在指 令管線的數個階段之後’才能取得在指令中編碼之資訊。 發明概沭 本發明之一實施例包含一微處理器。該微處理器包含一 分支預測表（BPT)，該BPT具有至少一個分支資料項。該等 至少一個分支資料項包含一預測攔位，用以指示一分支是 否被預測爲採取。該等至少一個分支資料項亦包含一過去 吞己錄暫存器’用以儲存過去記錄資訊。此外，該Βρτ包含 一預測更新邏輯電路，除了在靜態地堅定預測一分支時之 外，該預測更新邏輯電路都更新該預測攔位及該過去記錄 暫存器。 附圖簡述 若參照下文之詳細説明、最後的申請專利範園、及附圖 ，將可更完整地了解本發明之特徵、面向、及優點，這些 附圖有： 圖1是根據本發明的一微處理器之簡化實施例之方塊圖； 圖2是根據本發明一實施例的一分支預測表之方塊圖，其 中該分支預測表具有一資料項、及該分支預測表之其他結 構；以及 圖3疋根據本發明而分配一分支的一方法實施例之流程圖。 本發明之詳細説明 在下列的説明中，述及了諸多特定細節，使本發明得以 1^-----------裝----- - -- 訂---------線 (請先閱讀背面之注意事項再填寫本頁) -6-

經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（4 ) 被徹底了解。然而，對本門技術具有一般知識者當可了解 ，在沒有這些特定細節的情形下，仍可實施本發明。在某 些情形中，並未詳細示出一些習知的電路、結構、及技術 ，以免模糊了本發明。 本發明之一實施例包含一微處理器。該微處理器包含一 分支預測表（BPT)，該BPT具有至少一個分支資料項。該等 至少一個分支資料項包含一預測欄位，用以指示是否將一 分支預測爲採取。該等至少一個分支資料項亦包含一過去 記錄暫存器，用以儲存過去記錄資訊。該BPT進一步具有 一預測更新邏輯電路，除了在將一分支提示爲靜態地堅定 預測之外，該預測更新邏輯電路都更新該預測欄位及該過 去記錄暫存器。 該微處理器進一步包含一編譯器提示暫存器，該編譯器 提示暫存器具有一第一欄位，當該第一欄位被觸發時指示 一分支是靜態地堅定預測。該編譯器提示暫存器也包含一 第二欄位，當該第二欄位被觸發時指示一分支是否被預測 爲採取。該等至少一個分支資料項進一步包含一欄位（後文 中將該欄位稱爲“堅定預測/無條件的”（“Strongly Predicted/Unconditional” ；簡稱 SP/U)攔位。當發現一分夫 翅無條件的時，或者發現被插入分支資料項的一有條件的 分支具有堅定預測的編譯器提示時，即設定該SP/υ欄位。 當觸發該SP/U欄位時，指示一分支是堅定預測的、或一分 支是一無條件的分支。 該預測欄位係耦合到該編譯器提示暫存器之該第二欄位 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） I ^--------I I ! ^ ----it----I I I I (請先閱讀背面之注意事項再填寫本頁) 1223195 經濟部智慧財產局員工消費合作社印製 A7 B7__ 五、發明說明（5 ) 、及該預測更新邏輯電路。該預測欄位可自該編譯器提示 或自利用該預測更新邏輯電路的一動態分支預測器接收用 來指示一分支是否被預測爲採取之資訊。於觸發該SP/u欄 位時，即配置成禁止更新該過去記錄暫存器，或禁止更新 該過去記錄暫存器及該預測欄位。由於該SP/U欄位的觸發 ’所以禁止該動態預測器改變編譯器預測，或禁止改變編 譯器預測及過去記錄資訊。 現在已知如果使用編譯器提示，則通常將減少錯誤的預 測。本發明的微處理器實施例容許下列的情形：當編譯器 非常確定一分支的結果時，亦即在一堅定預測的分支之情 形時，用來指示一分支是否爲堅定預測的該編譯器提示暫 存器之執行權優先於晶片内建執行的動態預測演算法。利 用一種基於前文所述及該BPT中的該SP/U欄位之分配演算 法時，可提高預測的準確性。此外，藉由將編譯器預測資 訊儲存在該BPT，可以比在將分支指令解碼之後才能取得 預測資訊早許多之方式取得該編譯器預測資訊，這是因爲 要耗用較長的時間才能將該指令解碼。因此，本發明之該 微處理器實施例可決定是要採用原本晶片内建的動態預測 ’還是要在將指令解碼之前以編譯器靜態提示取代該動態 預測。 圖1是根據本發明的微處理器1〇〇的一簡化實施例之方塊 圖。微處理器100包含複數個管線階段，而圖中示出該等管 線階段中之管線階段102、104、及106。也被稱爲指令指標 產生管線階段的管線階段102產生用來指向指令快取記憶體 -8- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） !!! · I I —.1 — If — — — — — — (請先閱讀背面之注意事項再填寫本頁) 1223195 經濟部智慧財產局員工消費合作社印製 A7 B7___ 五、發明說明（6 ) 108中的一指令之指令指標。在被稱為提取階段的次一管線 階段104中，係根據前一管線階段中產生的指令指標，而自 指令快取記憶體1〇8提取一指令。在被稱為循環管線階段 106之次一管線階段中，擷取一指令並將該指令解碼。在並 未設有本發明之裝置及方法時’在循環管線階段106中將一 指令解碼之前，無法取得一編譯器預測提示。在根據本發 明的的該微處理器實施例中，如果先前已檢視過該分支， 且已在分支預測表（BPT) 140中分配了該分支，則可在提取 管線階段104中取得該編譯器預測提示。 BPT 140提供了最近預測的各分支之快取記憶體、以及諸 如先前執行的簡要過去記錄等對應的預測資訊、及（或）對 分支的預設及預測之成功與否。例如’ BPT 140的一分支資 料項可包含一預測欄位（圖中未示出），用以指示是否應採 取一分支。此外，該BPT之一分支資料項包含一分支類型 欄位，用以指示一分支是一呼叫（CALL)、返回（RETURN) 、或一普通的分支等。微處理器100具有一指令指標產生器 (Instruction Pointer Generator ;簡稱 IPG) 103，用以產生一指 令指標（Instruction Pointer ;簡稱IP)。該 IP 向 BPT 140及儲 存指令的指令快取記憶體（Instruction Cache ;簡稱1C) 108指 定一個新的指令。在管線式微處理器的許多實施例中，可 利用指令指標内提供之一標記值來存取BPT 140，且1C 108 採用對應的標記值來識別該快取記憶體中之快取線。 IPG 103除了將指令指標提供給BPT 140及1C 108之外，也 將指令指標提供給一目標位址快取記憶體（Target Address -9 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） --ί---------I I 裝---I *---- 訂---------線 (請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（8 ) 傳送到選擇裝置120之控制（選擇）信號。選擇裝置120根據 該信號之邏輯狀態’而選擇TAC 110及RSB 124提供的目標 位址中之一目標位址。例如，一分支命中BPT 140及TAC 110，且該分支被預測爲採取，而且該分支不屬於返回類型 。預測電路I12產生一個傳送到選擇裝置120之選擇信號’ 而該選擇信號造成選擇來自TAC 110之目標位址。選擇裝置 120將該目標位址提供給IPG 103的選擇裝置150之其中一個 輸入蜂。 選擇装置150具有另一耦合到一遞增器152之輸入埠’該 遞增器152將指令指標遞增諸如“1”之一預定値。遞增後的 指標被傳送回選擇裝置150，以便在需要提取次一循序指令 時利用該指標作爲一個新的指令指標。此外，選擇裝置150 具有兩個輸入埠，用以接收信號EXCEPTION TRAP及 BRANCH MISPREDICTION (BMISP)。 選擇装置150也具有複數個選擇輸入埠，用以接收複數個 選擇信號。這些選擇信號中的一個選擇信號是來自BPT 140 之採取/不採取（T/N)信號。其他的信號包含自“位於”管 線較遠處的各管線階段接收的一有效異常狀況信號（VALID EXCEPTION)及一有效分支錯誤預測信號（VALID BMISP) 〇 可將選擇裝置150配置成根據下列架構而將輸入到該選擇裝 置150的各指令位址信號分配優先順序，而在該架構中·· (1 )將第一優先順序授予自微處理器的一後端區段的一 EXCEPTION/TRAP指令位址信號；（2)將第二優先順序授予 亦自微處理器的該後端區段的一分支錯誤預測信號 -11 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公楚） ------------- ----.---.1 ^---------^ (請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（9 ) (BMISP)指令位址信號；（3)將第三優先順序授予自選擇裝 置120驅動到選擇裝置150的一目標指令位址信號；以及（4) 將第四優先順序授予由遞增器152產生的遞增後之指令指標 信號。根據該優先順序架構，如果並未觸發選擇信號 VALID BMISP及VALID EXCEPTION，且該分支被預測為採 取，則選擇裝置150在其一輸出埠上選擇自選擇裝置120接 收的目標位址。 一預測演算法以下列方式控制預測。當BPT 140指示一未 命中，且TAC 110指示一命中時，即將一分支預測為採取， 且選擇裝置120選擇來自TAC 110之目標位址，並將該目標 位址傳送到指令指標產生器103。如果有一BPT未命中及一 TAC未命中，則決定並無任何分支資料項。指令指標產生 器103遞增現有的指標，並將該遞增的現有指標傳送回選擇 裝置150。如果BPT命中且TAC未命中，則BPT指示該指令是 一返回類型，且預測電路112將一選擇信號驅動到選擇裝置 120，因而選擇來自RSB 124的一各別返回位址。然而，如 果在BPT 140及TAC 110中都命中，且該分支被預測為採取 ，則預測電路112使得選擇裝置120選擇來自TAC之目標位 址。 如果在BPT 140及TAC 110中都命中，但是該分支並未被 預測為採取，則微處理器根據遞增後的先前指標產生一個 新的指標，而提取快取記憶體108中之次一循序指令。當命 中BPT 140但並未命中TAC 110，且該指令是一般類型時， 可在將指令解碼之後，自該指令計算目標位址。 -12- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） --1-----------^--------- 訂---------線 (請先閱讀背面之注意事項再填寫本頁) 1223195 經濟部智慧財產局員工消費合作社印製 A7 五、發明說明（1〇 在本文所述的本發明之該微處理器實施例中，編譯器被 酉u«成將編澤器提示”編碼到一指令中，成爲兩位元的預 測資訊。係根據一分支被預測爲採取或不採取的可能性， p又疋編澤器示編碼所專用的該兩個位元。該兩個位元 編碼成用於分支預測的四種不同之機率··可能不採取、可 能採取、堅定的不採取、及堅定的採取預測。在下文的説 明中，分別將堅定的採取及堅定的不採取稱爲“靜態的採取 及靜4的不採取”，這是因爲利用編譯器所提供的靜態提 示時’更flb預測出該分支。將可能採取的及可能不採取的 分支分別稱爲“動態的採取，，及“動態的不採取，，，這是因爲 利用一動態預測器時，更能預測出該分支。在下文的説明 中，靜態的’’與“堅定的”以及“動態的，，與“可能的，，是可互 換使用的。 編譯器係利用程式特徵檔案法決定一“採取率，，，其中該 程式特徵檔案法以若干樣本資料集執行一程式，並收集分 支結果統計資料。該“採取率，，可自〇 %到1〇〇%。當該“採取 率係介於零與諸如約10%等的某一百分率“X”時，極有可 能“不採取”該分支，因而該兩個位元可將預測編碼成“靜態 的不採取”。當該“採取率”係介於約10%與諸如約50%等 的某一百分率“γ”時，可能“動態地不採取，，該預測。當該“ 採取率’’係介於約5 0 %與諸如約9 0 %等的某一百分率“ z，，時 ，可能“動態地採取”該預測。當該“採取率”係介於“ z，，與 諸如100%時，極有可能“靜態地採取，，該預測。 係根據與在微處理器中實施的動態分支預測器的準確性 ^張尺度適財關家標準（CNS)A4規格（2_iQ x 297公爱） -----1 I I I I I I .. · I I —ί I I Ϊ ^--! — ！·線 (請先閱讀背面之注意事項再填寫本頁) 13- 1223195 A7

之比較，而建立該等百分率値χ、γ、及z。 支預測器通常有90%的預測準確性。如果編_::古動 90%的準確性，則可利用編譯器提示來取代^ : 因此，當極有可能“採取，，_分支時 _ 測器。 經濟部智慧財產局員工消費合作社印製 位元來取代BPT動態預職的任何指;等兩個編碼 極有信心將採取一分支。 饤“，-是因爲編譯器 當碰到-“靜態的不採取，，分支時，通常不會有指令流改 A。因此，不需要將該分支緩衝儲存在Βρτ中。者一指令 :編碼的資訊指示有一個可能採取的或可能不採：的二 時’編譯器並不十分確定應採取或不採取該分支。在此種 情形中，利用BPT140來動態預測分支的行爲。動態預測利 用BPT中记錄的分支〈過去記綠來預測即將到來的分支之 結果。如果實施本文所述的本發明實施例之微處理器具有 可用的BPT預測（亦即動態預測），則該微處理器可利用該 BPT預測來決定應採取或不採取—分支。如果無法使用該 BPT預測，或微處理器想要取代該Βρτ預測，則該微處理器 :利用該兩個位元的編譯器提示之採取/不採取攔位來決 定應採取或不採取一分支。在本發明的一實施例中，該等 兩個編碼位元是一 4 1位元指令的一部分，且編譯器將該等 兩個編碼位元寫入該指令中，但本發明並不限於4〗位元指 $的範園。一指令的長度只要符合下列條件即可：每一指 令有將編譯器提示編碼所專用的至少兩個位元。 般而言’儲存在BPT中之分支是有可能造成指令流改變 之刀支。通常是將這些分支同時緩衝儲存在Βρτ及TAC。在 — r!------- 装——· C請先間讀背面之江意事項再填寫本頁) 訂· -破

本紙張尺度翻巾關家標準（CNS)A4規格（210 297公釐） 經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（12) 一將於本節後文中說明的分配程序之後’而在可自將指令 解碼而取得編譯器預測提示之前，系統之預設都將並未在 BPT中命中的分支預測為不採取。與“靜態不採取的，，分支 指令不同，較有可能在某一時點採取“動態不採取的”分支 指令。因此，係將與“動態採取的”或“動態不採取的”分支 儲存在BPT中。 對於一個常規的有條件的分支而言，可將目標位址插入 TAC中，而不將該目標位址插入BPT中。對於一個諸如“靜 態採取的”分支等的極有可能採取的分支而言’只要目標位 址是在TAC中，則分支的過去記錄是在BPT中或不在BPT中 是不重要的，因為預測時並不會使用該分支的過去記錄。 在本發明的一微處理器實施例中，當一位址命中TAC但並 未命中BPT時，自動將該分支預測為採取，而自命中的TAC 資料項中取得目標位址。然而，係將據以“靜態採取的，，提 示之呼叫及返回指令窝入BPT中，這是因為這兩類的分支 可能影響到返回堆疊缓衝器（RSB) 124。因此，可將呼叫及 返回資訊寫入BPT 140中，因而BPT 140可在將分支解碼之 前即提供呼叫/返回類型的資訊。 圖2示出一分支預測表（BPT) 200。對每一分支指令而言， BPT 200具有一分支資料項260。分支資料項260包含數個攔 位，這些欄位包括：一有效位元欄位240、一堅定預測/無 條件的（SP/U)欄位242、一預測攔位244、一分支類型欄位 (CALL/RETURN/REGULAR) 261、及一過去記錄暫存器 246。 在一實施例中，每一SP/U及預測欄位242及244分別包含1 -15· $紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ------%!----I 裝---I!訂---I-----線 (請先閲讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（13) 位元，而過去記錄暫存器246包含4位元。我們當了解，上 述各欄位的大小並不限於一特定數目的位元，而是可以不 同數目的位元來實施該等攔位。後文中將把SP/U及預測攔 位242及244稱為“SP/U位元242”及“預測位元244”。有效攔 位240指示資料項260中之分支是否有效。SP/U位元242指示 一分支為有條件的或無條件的，或者該分支是否被堅定預 測。常規的有條件的分支包含非返回及非呼叫類型的分支 。對一有條件的分支而言，預測通常係根據執行過去記錄 而隨著時間改變。 預測位元244及過去記錄暫存器246係耦合到一預測更新 邏輯電路248。預測更新邏輯電路248係耦合到模式過去記 錄表250。預測更新邏輯電路248可實施一種諸如“Tse-Yu Yeh兩階層預測演算法”等的兩階層預測演算法。若要得知 與此種演算法有關的更多資訊，請參閱T-Y. Yeh及Y. N. Patt 於 “Proceedings of the 19th International Symposium on Computer Architecture”，pp. 124-134，May，1992 發表的論文 “Alternative Implementations of Two-Level Adaptive Branch Prediction”。 通常是由預測更新邏輯電路248更新預測位元244及過去 記錄暫存器246。然而，對於一無條件的分支或靜態採取的 及靜態不採取的分支而言，該預測並不隨著時間而改變， 亦即該預測保持為採取的或不採取的。為了避免這些情形 中預測的改變，設定SP/U位元242的組態，使預測更新邏輯 電路248不會更新預測位元244及過去記錄暫存器246。 -16- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） --------I I I I » · I I I — I I i 訂--— — — — — I·線 <請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1223195 A7 B7 五、發明說明（14) SP/U位元242係經由一反相器262而耦合到三態緩衝器270 及272，而三態緩衝器270及272分別控制對預測位元244及 過去記錄暫存器246之窝入。當SP/U位元242被設定時，將 使預測更新邏輯電路2 4 8不會更新預測位元244及過去記錄 暫存器246，這是因為三態緩衝器270及272是三態的。反相 器262將來自SP/U位元242之邏輯信號反相，而產生了一個 傳送到三態緩衝器270及272的起動埠之邏輯”0·’。一旦 SP/U位元242被設定，則編譯器提示暫存器247的第二攔位 (T/N)280窝入預測欄位244的預測位元。然而，當SP/U位元 242被停止觸發為“0”時，三態緩衝器270及272可根據前文 所述之兩階層預測演算法，而以來自預測更新電路248之資 訊更新預測位元244及過去記錄暫存器246。 在根據本發明的該微處理器實施例中，當一分支是“靜態 採取的”時，將該過去記錄暫存器設定為“1111”。當該過去 記錄暫存器的所有位元都被設定為“ 1 ”時，一分支被預測 為採取。模式過去記錄表250具有一對應於以硬體方式接線 為“ 1 ”之“ 1111”之資料項290，以便在該過去記錄暫存器的 内容是“ 1111”時，固定地預測為採取。因而指示始終採取 一分支。當一分支是“靜態不採取的”時，該過去記錄暫存 器被設定為“ 〇〇〇〇”。模式過去記錄表250具有一對應於以硬 體方式接線為“ 〇 ”的“ 〇〇〇〇”之資料項292，以便在該過去記 錄暫存器的内容是“ 〇〇〇〇”時，固定地預測為不採取。分別 以硬體方式將資料項“ 〇〇〇〇”及“ 1111”接線為“ 0 ”及“ 1 ”時， 預測將不會改變，而與自執行記錄得知模式過去記錄表250 -17- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） --：----------- 裝--------:-訂-----I---線 (請先閱讀背面之注意事項再填寫本頁) 1223195 A7 B7 五、發明說明（15 ) 中之各資料項並因應地修改其預測之方式不同。 因此，對於“靜態採取的”分支而言，只要該分支仍然存 在於BPT中，則SP/U位元242被設定，且該過去記錄暫存器 保持原來的値“1111”。對於“靜態不採取的”分支而言， SP/U位元242被設定，且該過去記錄暫存器保持原來的値 “0000”。如果編譯器提示指示有一個‘‘動態採取的”或“動態 不採取的”預測，則清除SP/U位元242，採用利用預測位元 244之常規動態預測，且預測更新邏輯電路248更新分支過 去記錄暫存器246。 圖3是與根據本發明一實施例而分配一分支的一程序有關 之流程圖。該程序開始於步驟301，且該程序自此流到決定 步驟302。在決定步驟302中，利用編譯器提示（亦即兩個編 碼位元）決定一分支是否爲靜態的。如果該分支不是靜態的 ，而是動態的，則本程序流到步騍304。在步驟304中，更 新BPT及TAC。該更新通常包含：將上次使用的一目標位址 寫入TAC ;以及將分支資訊寫入BPT。將SP/U位元242設定 爲“ 0 ”，以便讓預測更新邏輯電路更新過去記綠暫存器及 預測位元。自此時開始使用動態預測。如果該分支被預測 爲採取，則將該過去記綠暫存器的内容設定爲其起始値 “ 1111”（或設定爲可能得到一個被採取的預測之某一模式値 )。如果該分支被預測爲不採取，則將該過去記綠暫存器的 内容設定爲其起始値“ 0000”（或設定爲可能得到—個不被採 取的預測之某一模式値）。 然而，如果在決定步驟302中決定該分支是靜態的，則本 -18- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） (請先閱讀背面之注意事項再填寫本頁) 裝 — r訂---------碎 經濟部智慧財產局員工消費合作社印製 經濟部智慧財產局員工消費合作社印製 1223195 A7 -----^___ 五、發明說明（16 ) 程序自決足步驟302流到決定步驟306，此時決定該分支是“ 知取的”或是“不採取的，，。如果該分支是“不採取的，，，亦 即如果該分支是“靜態不採取的，，，則本程序流到步驟3〇8。 在BPT中不執行任何分配。當一分支被提示爲堅定不採取 的時，並不將該分支的資訊插入預測表中，這是因 預設的分支預測已經是“不採取的”。然而，如果該分^被 採取，則本程序流到決定步驟31〇，此時決定該分支是否屬 於“呼叫”或“返回，，類型。如果該分支並不屬於呼叫或返回 類型，則本程序流到步驟311，此時更新TAC。如同在“靜 態採取的”情形中，當極有可能採取一分支時，即進行上述 的步驟，這是因爲不需要在Βρτ中浪費空間來儲存過去的 記錄。 如果孩分支屬於呼叫或返回類型，則本程序流到決定步 驟313，此時決疋該分支是否屬於呼叫類型。如果該分支屬 於呼叫類型，則本程序流到步驟312，此時更新Βρτ及TAC 。將過去記錄暫存器的資訊設定爲其起始値“ lm”，並將 SP/U位兀242設定爲‘4’’。更新BPT，以便記錄與諸如呼叫 、返回、或常規等的分支類型。利用該分支類型資訊來更 新其他的分支預測結構。例如，在進行預測之後，可利用“ 類型”資訊來更新返回堆疊緩衝器（RSB)。在一“呼叫，，之後 ，將返回位址推送到該RSB。在一“返回，，之後，即移出堆 疊最上方的資料項。 然而’如果在決定步驟313中決定該分支屬於返回類型， 則本程序流到步驟314，此時除了 一項例外之外，採取與步 -19 - 本紙張尺度適用中國國家標準（CNWA4規格x 297"^- — — — — — — 1 裝· — — f 訂·— —，— — — ··^ (請先閱讀背面之注意事項再填寫本頁) 1223195 A7 五、發明說明（17 驟312中動作相同的動作。並不更新TAC，這是因爲係利用 取代TAC的來預測返回位址。 在前文的詳細説明中，係參照一些特定實施例而説明本 發明。然而’我們當了解，在不脱離申請專利範圍所述的 本發明之廣義精神及範圍下，仍可對本發明作出各種修改 及改變。因此’本説明書及圖示被视爲舉例，而不是對本 發明加以限制。 (請先閱讀背面之注意事項再填寫本頁) 裳i!i!f訂！ — I·錄 經濟部智慧財產局員工消費合作社印製 -20 - 本紙張尺度適用辛國國家標準（CNS)A4規格（210 X 297公釐）

Claims (1)

1. & #〇J^〇S388號專利申請案 W文穿料纖®替拖太 舞·專利範圍替換本(93年2月）

   申请專利範圍 一搜儆慝理器 有焊 無請 變‘ 更員 實明 質示

   2. 是之 否月 准叱 予日 修修 正正 ?本 一分支預測表，該分支預測表具有： 至少一個分支資料項，該至少一個分支次 用來指示-分支是否被預測為採取之一預：椚：包含 用來儲存過去記錄資訊之一過去記錄暫存器/以、及 一預測更新單元，更新該預測襴位與谧以及 地堅定預測一分支時更新之過去記錄暫存器；及靜怨 一具有一第一襴位之編譯器提示，當觸發該第—抵士 時，該第一欄位指示一分支是被靜態地堅定預測。]位 如申請專利範圍第1項之微處理器，該編譯器提示進一 步包含弟一襴位，當該弟二攔位被觸發時，讀^ 一 位指示一分支被預測為採取。 * 3 ·如申請專利範圍第1項之微處理器，進一步包含—輪人 到該預測更新單元之模式過去記錄表。 4 ·如申請專利範圍第1項之微處理器，該等至少一個分支 資料項包含一堅定預測/無條件的襴位，用以指示—分 支是否為一堅定預測的分支及一無條件的分支中之—種 分支。 5 ·如申請專利範圍第4項之微處理器，該堅定預測/無條 件的欄位係耦合到該編譯器提示分支之該第一襴位。 6 ·如申請專利範圍第2項之微處理器，該預測襴位係輪合 到該編譯器提示之該第二欄位。 7 .如申請專利範圍第1項之微處理器，該等至少一個分支 資料項包含一有效欄位，用以指示該分支資料項是否有 AS B8 一 效。 1申胡專利範圍第4項之微處理器，該等至少-個分支 貝料項包含-用來指示該分支是否為〆呼叫、返回、及 常規類型的其中一種類型之襴位。 9·如=請專利範圍第8項之微處理器，當決定該分支為被 堅定預測為採取，且該分支不屬於呼叫或返回類型時， 更新一目標位址快取記憶體。 1 〇 ·如中4專利|(L圍第9項之微處理器，當決定該分支為被 堅疋預測為採取，且該分支屬於呼叫類型時，更新該分 支預測表及-目標位址快取記憶體，將該過去記錄暫存 器的起始值设定為一採取類型，並觸發該預測及sp/u欄 位。 1 1 ·如申請專利範圍第9項之微處理器，當決定該分支為被 堅定預測為採取，且該分支屬於返回類型時，更新該分 支預測表，將該過去記錄暫存器的起始值設定為一採取 類型，觸發泫預測及SP/ u襴位，且並不更新該TAC。 1 2 ·如申請專利範圍第4項之微處理器，當該分支被預測為 動態採取時，更新該分支預測表及一目標位址快取記憶 月豆（TAC)，停止觸發泫SP/ U欄位，且將該過去記錄暫存 器的起始值設定為一採取類型。 1 3 ·如申請專利範圍第4項之微處理器，當該分支被預測為 動態不採取時，更新該分支預測表及一目標位址快取記 憶體（TAC)，停止觸發該sp/u欄位，且將該過去記綠暫 存器的起始值設定為一不採取類型。 1223195 A8 B8 C8 ------ D8_______ _ 六、申請專利範圍 1 4. 一種在一微處理器中分配一分支之方法，該方法包含下 列步驟： 檢查一編譯器提示，而決定一分支是否被堅定預測為 採取；以及 如果該分支被堅定預測為採取且屬於一呼叫類型，則 更新一分支預測表及一目標位址快取記憶禮（TAC)， 將一過去記錄暫存器的起始值設定為一採取類型；以 及 觸發一預測欄位及一堅定預測/無條件的（SP/U)欄位 〇 1 5 ·如申請專利範圍第1 4項之方法，進一步包含下列步驟： 當該分支被堅定預測為採取且屬於一返回類型時， 更新該分支預測表； 將一過去纟己錄暫存為的起始值設定為一採取類型；以 及 觸發該預測襴位及該SP/ U欄位。 1 6 ·如申請專利範圍第1 4項之方法，進一步包含下列步驟： 當決定該分支為被堅定預測為採取，且該分支不屬於 呼叫或返回類型時，更新該TAC。 1 7 ·如申請專利範圍第1 4項之方法，進一步包含下列步驟· 當該分支被動態地預測為採取時，更新該分支預測表 及該TAC ; 停止觸發該SP/ U欄位，且將一過去記錄暫存器的起妒 值設定為採取。 α -3 - 本紙張尺度適用中國國家標準(CNS) Α4規格(210 X 297公釐) C8 D8 申請專利範圍 •如申請專利範圍第1 4項之方法，進一步包含下列步驟·· 如果該分支被動態地預測為不採取時，則 更新該分支預測表及該TAC， 將該過去記錄暫存器的起始值設定為不採取，以及 停止觸發該SP/U攔位。 19.—微處理器，包含： 一編譯器提示暫存器，該編譯器提示暫存器包含一用 來指示一分支是否被堅定預測之第一攔位、及一用來指 不該分支是否被預測為採取之第二欄位；以及 一分支預測表，該分支預測表包含： 一預測更新單元； 至少一個分支資料項，該等至少一個分支資料項包含 —用來指示一分支是否被預測為採取之預測欄位、及一 用來儲存過去記錄資訊之過去記綠暫存器；以及 20. 21. 泫預測更新單元更新該預測攔位與可避免在靜態地堅 定預測一分支時更新之過去記綠暫存器。 如申請專利範圍第19項之微處理器，進一步包含一耦合 到該預測更新單元之模式過去記綠表。 如申請專利範圍第20項之微處垤器，該等至少一個分支 資料項包含-堅定預測/無條件的襴位，用以指示一分 支是否為-堅定預測的分支及—無條件的分支中之一種 分支。 22.如申請專利範圍第21項之微處垤器，該等至少一個分支 資料項包含一用來指示該分支是否為一呼叫、返回、及 -4- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公------ 1223195 六、 23 2 4 25 26 27 28 A8 B8 C8 ------- D8 __申请專利範圍 常規類型的其中一種類型之襴位。 •如申請專利範圍第2 2項之微處理器，當決定該分支為被 堅足預測為採取，且該分支屬於呼叫類型時，更新該分 支預測表及一目標位址快取記憶體，將該過去記錄暫存 器的起始值設定為一採取類型，並觸發該預測及SP/U欄 位。 •如申請專利範圍第2 2項之微處理器，當決定該分支為被 堅疋預測為採取，且該分支屬於返回類型時，更新該分 支預測表’將該過去記錄暫存器的起始值設定為一採取 類型’觸發該預測及SP/υ襴位，且並不更新該TAC。 •如申請專利範圍第2 2項之微處理器，當決定該分支為被 堅足預測為採取，且該分支不屬於呼叫或返回類型時， 更新一目標位址快取記憶體。 •如申請專利範圍第2 1項之微處理器，當該分支被預測為 動態採取時，更新該分支預測表及一目標位址快取記憶 m(TAC)，停止觸發该SP/U襴位，且將該過去記錄暫存 器的起始值設定為一採取類型。 •如申請專利範圍第2項之微處理器，其中該預測更新單 7C避免在分支項中編譯器提示中靜態堅定預測欄位觸發 時更新違預測爛位及過去記錄暫存器。 •如申請專利範圍第2項之微處理器，其中該編譯器提示 由一編譯器於定義指令後產生，且該提示係編碼於指令 中，供稍後由該微處理器解碼時用。 -5- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐) 1223195 第089108388號專利申請案 中文圖式替換頁(93年2月） 公告本 年月3雙正93. 2. 18 補充 “'丨1 __ .......................

   斗 ^ 1t^ sc 斜涔驷t ^^Llt^ exception/trap ^^¾¾¾¾¾^ CDls&Jybus ¾今洚背 ^.0 +1 152/ 益命 ^¾ Μ IPGΜ g Τη <- Μ FET L1洚钾 WAY MUX 100 涵 Μ Fl〇T