[發明專利]針對已調度匯編代碼的控制流圖重構方法

有效

• 申請號: 201310565945.3
• 申請日: 2013-11-14
• 公開（公告）號: CN103577242B
• 公開（公告）日: 2016-11-02
• 發明（設計）人: 應歡;王雷歐;王東輝;洪纓
• 申請（專利權）人: 中國科學院聲學研究所
• 主分類號: G06F9/45
• 分類號: G06F9/45;G06F9/44
• 代理公司: 北京億騰知識產權代理事務所 11309
• 代理人: 陳霽

技術領域

本發明涉及數字數據處理領域，具體涉及一種針對已調度匯編代碼的控制流圖重構方法。

背景技術

在數字信號處理器領域中，很多軟件都是針對具體的目標體系結構特征，以匯編的形式實現。這些軟件難以理解和維護，也不易完成不同體系結構之間的移植。在逆向工程、二進制翻譯領域，完成這些工作的第一步是對源匯編程序控制流的重構。

在編譯器設計領域，很多代碼優化技術都是直接針對匯編代碼進行，主要包括：鏈接時程序全局分析及優化、代碼壓縮、二進制翻譯等。這些優化技術都是基于匯編代碼的控制流圖(Control?Flow?Graph，CFG)完成。然而，編譯器生成的匯編代碼具有特定的體系結構特征，其涵蓋的調度信息使得匯編代碼的CFG的構建更加復雜。

對于具有超長指令字架構（very?long?instruction?word,VLIW）結構的微處理器，分支指令是提高其性能的一個重要障礙。等待分支結果的延遲會造成流水線停頓，從而降低指令并行度。硬件設計中的延遲槽結構有助于解決此類控制相關而帶來的性能問題，并與編譯器配合完成分支指令的延遲槽調度。現有技術中，為了減少分支指令帶來的流水線停頓周期，將一些與分支指令不相關的有用指令填充到該分支指令后的延遲槽中，以提升處理器的性能。這些指令不受分支指令結果的影響，無論分支成功與否，流水線都會執行這些指令。因此，在還原源程序的控制流時，常用方法是，根據分支指令的執行周期數，將其延遲槽中的所有指令前移，由此得到源程序執行時機器無關的控制流。然而，對于一些高性能的處理器，其優化的編譯器允許延遲槽調度的對象是分支指令。對于這種延遲槽中有其他的分支指令的情況時，現有的控制流分析方法不再適用。

針對帶延遲槽的分支指令的匯編程序的CFG的建立，一般方法是：首先根據子片段信息將匯編代碼分塊，其次不考慮延遲槽，將各個基本塊之間的簡單跳轉關系添加至CFG中，最后，針對帶有延遲槽的分支指令，通過多次迭代，在CFG中添加所有可能的跳轉邊，但這種方法僅僅將源匯編代碼按基本塊分割，添加可能的跳轉分支，從中很難恢復源程序的執行序。

對上述一般方法做改進后，提出的方法是：針對調度后的匯編代碼提出建立控制數據流圖(Control?and?Data?Flow?Graph，CDFG)的算法，該算法是在上述一般方法的基礎上生成CFG，在處理帶有延遲槽的指令時，通過引入虛擬寄存器來打破原指令的多周期執行，完成去延遲槽操作。但是該方法在解決多周期指令的去延遲槽操作時，引入了較多的額外指令，效率較低。

發明內容

本發明的目的是提供一種針對已調度匯編代碼的控制流圖重構的方法。

本發明提供了一種針對已調度匯編代碼的控制流圖重構方法，包括：

對源程序進行靜態分析，根據全局延遲槽列表信息，獲取源程序所有可能的執行路徑，由此構建指令流圖；其中，指令流圖中的每個結點代表一條指令，每一條邊代表一條指令到另一條指令一種的可能執行序關系；

遍歷所述指令流圖中的各個結點，根據所述各個結點的入度和出度信息，創建基本塊，生成控制流圖；

基于控制流圖，分析各基本塊中的各個執行包，對所述執行包建立匯編級數據依賴圖；根據源體系結構指令集信息，確定所述執行包中各條指令的時間戳信息；

根據所述各條指令的時間戳信息，進行指令的跨塊或跨包移動；

根據所述匯編級數據依賴圖，修改所述各條指令的時間戳信息；根據各條指令修改后的時間戳信息，重排序所述各條指令，由此復原所述程序中每條指令的等價執行。

優選地，對源程序進行靜態分析，初始化指令隊列和全局延遲槽列表，添加初始指令至指令隊列，在指令隊列為非空時，根據所述全局延遲槽列表，分析處理指令隊列中的隊首指令，建立所述隊首指令與其所有可能的直接后繼指令的連接關系，并將非空的所有可能的直接后繼指令加入所述指令隊列，在所述指令為分支指令時，將該分支指令的延遲槽信息添加至全局延遲槽列表中，重復上述操作，直到指令隊列為空，由此生成指令流圖。

優選地，廣度優先遍歷所述指令流圖中的各個結點，以所述指令結點的入度和出度是否大于1，作為基本塊邊界劃分的依據，以此合并指令序列，創建基本塊，并添加所述指令流圖中的邊信息，生成控制流圖。

優選地，通過對所述執行包建立匯編級數據依賴圖，描述執行包中的各條指令間的寫后讀依賴和/或讀后寫依賴。