[發明專利]一種實現間接轉移關聯軟件預測的方法及裝置

在審

• 申請號: 201611208034.5
• 申請日: 2016-12-23
• 公開（公告）號: CN106843812A
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 程旭;黃明凱;劉先華
• 申請（專利權）人: 北京北大眾志微系統科技有限責任公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京安信方達知識產權代理有限公司11262
• 代理人: 韓輝峰,李丹

技術領域

本發明涉及動態翻譯技術，尤指一種動態翻譯系統中實現間接轉移關聯軟件預測的方法及裝置。

背景技術

動態二進制翻譯技術(dynamic translation)廣泛應用于指令系統模擬、二進制插樁、動態優化、程序行為分析等領域。在多種應用場景下，性能是翻譯系統需考慮的重要指標。其中，控制轉移指令的處理方法是影響動態翻譯系統性能的重要因素。當控制轉移指令執行時，其獲取到的轉移目標是一個源程序計數器地址(SPC，Source Program Counter，簡稱為源地址)，需要將其轉換為相應的目標程序計數器地址(TPC，Target Program Counter，簡稱為目標地址)，翻譯系統才可正常執行。控制轉移指令一般可分為條件轉移指令、直接跳轉指令與間接轉移指令(IB，Indirect Branch)。對于轉移目標固定的條件轉移指令與直接跳轉指令，翻譯系統可使用代碼塊鏈接技術來降低開銷；而間接轉移指令的轉移目標在運行時才可以確定，且轉移目標不固定，因此每次執行時均需進行一次源地址(SPC)到目標地址(TPC)的地址轉換操作。圖1為現有翻譯系統處理間接轉移指令的流程示意圖，如圖1所示，由于間接轉移指令在每次執行時都需根據其當前的轉移目標進行地址轉換，因此進行大量的地址轉換操作導致了巨大的性能開銷，使得間接轉移指令的處理過程成為主要的系統性能開銷。

動態二進制翻譯系統一般會維護一個SPC-TPC的映射表，在源地址產生后，運行一個哈希(Hash)查表例程來進行地址轉換，然后再跳轉至相應的目標地址。但進行一次哈希查表需要10條以上指令，導致較大的開銷。

軟件預測法可以在一定程度上避免哈希查表帶來的額外開銷，即在轉移目標的SPC產生后，進入一條軟件預測鏈與預設的若干目標進行匹配，若匹配成功則直接跳轉，稱為預測成功。但是，軟件預測法的預測準確率一般較低，從而制約了其對整體性能的提升。圖2為現有軟件預測的方法示意圖，如圖2所示，在獲取到間接轉移指令的轉移目標的源地址后，需要進行若干次的比較-跳轉的預測操作。其中，每一個比較跳轉語句稱為一個預測槽(Prediction Slot)，所比較的目標稱為預設目標，多個串行比較的預測槽稱為一條“預測鏈”。若預測成功，則直接跳轉到相應的目標代碼塊，如果預測失敗，則按照圖1所示的現有的翻譯系統處理間接轉移指令的方法進行處理。現有軟件預測法的主要問題是預測準確率較低，直接增加軟件預測鏈上的預測槽個數可一定程度上提升準確率，但同時增加了預測時需進行的“比較”操作的次數，導致單次預測開銷上升，無法提升性能。

此外，目前還出現了一些軟硬件協同的優化方案，如在CPU流水線中新增一個跳轉地址查找表，或者新增一個按內容訪問的相聯存儲器(CAM，Content-Associated Memory)，但這些方案均需改動硬件或指令系統，通用性較差，無法直接在已有平臺上實現。

綜上所述，在現有的動態翻譯系統中，間接轉移指令往往占用大量的系統性能開銷，現有的處理方法存在指令開銷過大、預測準確率低及平臺應用的通用性較差等問題，間接轉移指令占用主要系統開銷的問題依舊未得到有效處理。

發明內容

為了解決上述技術問題，本發明提供一種實現間接轉移關聯軟件預測的方法及裝置，能夠簡單、有效的降低間接轉移指令對系統性能開銷的占用。

為了達到上述發明目的，本發明公開了一種實現間接轉移關聯軟件預測的方法，包括：

對每條間接轉移指令進行軟件預測，當軟件預測失敗次數大于熱點指令閾值時，確定該間接轉移指令為難預測的熱點間接轉移指令；

對所述難預測的熱點間接轉移指令的控制流圖進行寬度遍歷，獲取到達該熱點間接轉移指令的路徑；

當獲取到達熱點間接轉移指令的路徑滿足預先設置的路徑條數時，為到達所述熱點間接轉移指令的每一路徑復制相應的代碼副本；

為每一代碼副本在預測槽中填入相應的預測目標，以形成相應的軟件預測鏈。

進一步地，為每一代碼副本在預測槽中填入相應的預測目標具體包括：為每一代碼副本的熱點間接轉移指令，統計其轉移目標，當轉移目標出現的次數大于熱點目標閾值時，在每一代碼副本的預測槽填入相應的預測目標。

進一步地，當軟件預測鏈形成后，該方法還包括：在軟件預測失敗時，進入哈希Hash查表例程。

另一方面，本申請還提供一種實現間接轉移關聯軟件預測的裝置，包括：預測判斷單元、路徑獲取單元、代碼復制單元及預測鏈單元；其中，