[發明專利]消除內存訪問沖突的編譯裝置及其實現方法

無效

• 申請號: 201010577313.5
• 申請日: 2010-12-08
• 公開（公告）號: CN102043659A
• 公開（公告）日: 2011-05-04
• 發明（設計）人: 肖賀;孔吉;劉佩林
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F9/45
• 分類號: G06F9/45;G06F9/50
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王錫麟;王桂忠

1.一種消除內存訪問沖突的編譯裝置，其特征在于，包括：前端語言分析單元、內存變量分析單元、內存沖突消除單元和轉換輸出單元，其中：前端語言分析單元與內存變量分析單元和內存沖突消除單元相連接并傳輸由源程序轉換的中間語言序列、內存模型與內存操作信息和源文件函數依賴樹，內存變量分析單元與內存沖突消除單元相連接并傳輸變量內存分配和內存塊操作信息，內存沖突消除單元與轉換輸出單元相連接并傳輸經過內存分配優化的中間語言信息，轉換輸出單元輸出最終的可執行代碼。

2.根據權利要求1所述的消除內存訪問沖突的編譯裝置，其特征是，所述的前端語言分析單元包括：內存配置組件、語言分析組件和文件函數關系組件，其中：內存配置組件與內存變量分析單元相連接并通過內存操作信息表和內存模型描述表傳遞內存操作信息和內存模型，語言分析組件將源程序轉換為中間語言序列并分別傳遞給內存變量分析單元和內存沖突消除單元，文件函數關系組件分析源程序中各文件的函數依賴關系并以源文件函數依賴樹的形式傳遞給內存沖突消除單元；所述的內存操作信息表包括：數學運算指令功能、操作數個數、操作數類型、尋址模式、數據寬度以及執行開銷；所述的內存模型描述表包括內存的總大小、內存分區的個數、各個內存分區的起始地址和大小。

3.根據權利要求1所述的消除內存訪問沖突的編譯裝置，其特征是，所述的內存變量分析單元讀取并分析記錄中間程序包含的所有的內存變量及其操作，該內存變量分析單元包括：內存變量分配器和變量分析組件，其中：內存變量分配器分析由前端語言分析單元生成的中間語言序列中的內存變量信息并采用動態分配或靜態分配以變量內存分配表的形式傳遞給變量分析組件，內存變量分析單元通過變量內存分配表來分析每一個程序基本塊中的內存操作信息并記錄到內存塊操作表中，其中：動態分配是指：內存變量分配器通過唯一確定且記錄到變量內存分配表中的分配標識以跟蹤記錄內存變量的名稱以及生存周期信息；靜態分配是指：內存變量分配器標識該變量生存周期為全局并記錄到變量內存分配表中；所述的變量內存分配表包括：變量標識、變量名、變量尺寸、變量生存周期、變量分割以及內存分配，其中：變量標識是區別不同變量的唯一標識；變量尺寸記錄變量的大小信息；變量生存周期記錄變量的生存周期，包括變量的分配時刻以及變量的釋放時刻，在初始階段對于全局變量來說，分配時刻即程序開始，釋放時刻是程序終止；變量分割記錄變量經過變量分割變換模塊后的新信息，包括分割數量，每個分割的變量重命名，以及各分割的內存分配；所述的內存塊操作表中的每一個表項標識基本塊中內存操作的相關信息；相關信息包含：源內存操作數的個數，每個源內存操作數的大小、變量類型和操作數更新方式，目標內存操作數的個數，每個目標內存操作數的大小、類型和操作數更新方式，內存操作的類型。

4.根據權利要求1所述的消除內存訪問沖突的編譯裝置，其特征是，所述的內存沖突消除單元包括：變量分割組件、全局內存分配組件和尋址模式選擇組件，其中：變量分割組件接收由前端語言單元傳遞的中間語言序列，通過分析中間程序中存在的內存沖突，對符合分割模型的變量進行分割和重命名操作，同時更新變量內存分配表和內存塊操作表信息并分別輸出至全局內存分配組件和尋址模式選擇組件；全局內存分配組件讀取更新后的內存分配表并根據其中的內存變量的大小，生存周期采用優化算法對所有的內存變量進行分配并輸出至尋址模式選擇組件；尋址模式選擇組件根據內存塊操作表的信息，以基本塊為單位為數組形式的變量分配尋址模式，中間程序依次通過上述三個組件的轉換后，內存沖突消除單元輸出經過內存分配優化的中間程序和一個變量鏈接文件，該變量鏈接文件包括：每個內存分區的標識、內存分區的起始地址、分配到該內存的變量信息；為了減小內存的碎片，分配到各內存分區的變量按照變量大小從大到小的順序依次進行分配；變量信息包括變量名，變量的對齊模式、變量的大小。

5.根據權利要求1所述的消除內存訪問沖突的編譯裝置，其特征是，所述的轉換輸出單元，輸入為變量鏈接表和中間程序，通過轉換最終輸出機器可執行的程序代碼。

6.一種根據上述任一權利要求所述裝置的實現方法，其特征在于，包括以下步驟：

第一步：用戶編譯源程序，對需要進行內存分配調度的變量結構通過內存變量分配器進行分配，使得編譯器能夠顯式識別所有需要內存分配調度的變量；

第二步：用戶使用本發明的一種簡潔、易行且直觀的內存操作和內存模型描述方法對處理器支持的內存操作、尋址模式以及內存的模型進行描述；用戶只需要按照規范填入規范化的表格就可完成對內存操作以及內存模型的描述；

第三步：將用戶對內存操作以及內存模型的描述信息提取出來，并分別組織成具有良好接口、同時有利于編譯器解析的內存操作信息結構和特定內存的內存模型；

第四步：用戶輸入需要編譯的源程序和源程序的文件依賴關系；根據用戶編譯的文件依賴關系構造一棵源文件函數依賴樹；

第五步：源程序通過前端語言單元編譯轉換成編譯器通用的一種中間程序，在這一步中，可以實施多種編譯優化策略，包括對內存操作的調度，以消除內存操作之間存在的因數據相關而產生的沖突；

第六步：將由內存變量分配器分配的內存變量存放在變量內存分配表中；

第七步：結合第三步生成的內存操作信息結構，以及第六步生成的變量內存分配表，分析中間程序中對應內存變量的操作行為，并以基本塊的形式構建內存塊操作表；

第八步：根據第七步生成的內存操作表中各個內存變量的操作類型，通過變量分割模塊檢測各個內存塊操作表項是否匹配分割模型，對于符合模型的內存變量進行變量分割和重命名；

第九步：根據第四步生成的源文件函數依賴樹，找到發生分割重命名的基本塊與變量，并找到依賴關系中該基本塊的所有后續基本塊中對此分割重命名變量的所有引用，對它們也依次進行更新；

第十步：重復第八步和第九步，直到完成所有滿足模型的變量分割與重命名，同時更新變量內存分配表；

第十一步：根據變量內存分配表、內存塊操作表通過全局優化模塊進行內存變量全局優化分配；一種全局優化的方法是采用遺傳算法計算出內存分配的優化解；根據算法所找到的最優解更新變量內存分配表和內存塊操作表；

第十二步：根據內存塊操作表的信息中各個內存塊操作的源和目的操作數的更新方式，結合第三步中的內存操作結構信息中描述的尋址模式，由尋址模式分配組件選擇合適的尋址模式；

第十三步：根據最終的變量內存分配表生成變量鏈接文件；

第十四步：根據變量鏈接文件將中間程序生成最終生成機器可執行程序。