[發(fā)明專利]消除內(nèi)存訪問(wèn)沖突的編譯裝置及其實(shí)現(xiàn)方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010577313.5
• 申請(qǐng)日: 2010-12-08
• 公開(kāi)（公告）號(hào): CN102043659A
• 公開(kāi)（公告）日: 2011-05-04
• 發(fā)明（設(shè)計(jì)）人: 肖賀;孔吉;劉佩林
• 申請(qǐng)（專利權(quán)）人: 上海交通大學(xué)
• 主分類號(hào): G06F9/45
• 分類號(hào): G06F9/45;G06F9/50
• 代理公司: 上海交達(dá)專利事務(wù)所 31201
• 代理人: 王錫麟;王桂忠

1.一種消除內(nèi)存訪問(wèn)沖突的編譯裝置，其特征在于，包括：前端語(yǔ)言分析單元、內(nèi)存變量分析單元、內(nèi)存沖突消除單元和轉(zhuǎn)換輸出單元，其中：前端語(yǔ)言分析單元與內(nèi)存變量分析單元和內(nèi)存沖突消除單元相連接并傳輸由源程序轉(zhuǎn)換的中間語(yǔ)言序列、內(nèi)存模型與內(nèi)存操作信息和源文件函數(shù)依賴樹(shù)，內(nèi)存變量分析單元與內(nèi)存沖突消除單元相連接并傳輸變量?jī)?nèi)存分配和內(nèi)存塊操作信息，內(nèi)存沖突消除單元與轉(zhuǎn)換輸出單元相連接并傳輸經(jīng)過(guò)內(nèi)存分配優(yōu)化的中間語(yǔ)言信息，轉(zhuǎn)換輸出單元輸出最終的可執(zhí)行代碼。

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

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

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

5.根據(jù)權(quán)利要求1所述的消除內(nèi)存訪問(wèn)沖突的編譯裝置，其特征是，所述的轉(zhuǎn)換輸出單元，輸入為變量鏈接表和中間程序，通過(guò)轉(zhuǎn)換最終輸出機(jī)器可執(zhí)行的程序代碼。

6.一種根據(jù)上述任一權(quán)利要求所述裝置的實(shí)現(xiàn)方法，其特征在于，包括以下步驟：

第一步：用戶編譯源程序，對(duì)需要進(jìn)行內(nèi)存分配調(diào)度的變量結(jié)構(gòu)通過(guò)內(nèi)存變量分配器進(jìn)行分配，使得編譯器能夠顯式識(shí)別所有需要內(nèi)存分配調(diào)度的變量；

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

第三步：將用戶對(duì)內(nèi)存操作以及內(nèi)存模型的描述信息提取出來(lái)，并分別組織成具有良好接口、同時(shí)有利于編譯器解析的內(nèi)存操作信息結(jié)構(gòu)和特定內(nèi)存的內(nèi)存模型；

第四步：用戶輸入需要編譯的源程序和源程序的文件依賴關(guān)系；根據(jù)用戶編譯的文件依賴關(guān)系構(gòu)造一棵源文件函數(shù)依賴樹(shù)；

第五步：源程序通過(guò)前端語(yǔ)言單元編譯轉(zhuǎn)換成編譯器通用的一種中間程序，在這一步中，可以實(shí)施多種編譯優(yōu)化策略，包括對(duì)內(nèi)存操作的調(diào)度，以消除內(nèi)存操作之間存在的因數(shù)據(jù)相關(guān)而產(chǎn)生的沖突；

第六步：將由內(nèi)存變量分配器分配的內(nèi)存變量存放在變量?jī)?nèi)存分配表中；

第七步：結(jié)合第三步生成的內(nèi)存操作信息結(jié)構(gòu)，以及第六步生成的變量?jī)?nèi)存分配表，分析中間程序中對(duì)應(yīng)內(nèi)存變量的操作行為，并以基本塊的形式構(gòu)建內(nèi)存塊操作表；

第八步：根據(jù)第七步生成的內(nèi)存操作表中各個(gè)內(nèi)存變量的操作類型，通過(guò)變量分割模塊檢測(cè)各個(gè)內(nèi)存塊操作表項(xiàng)是否匹配分割模型，對(duì)于符合模型的內(nèi)存變量進(jìn)行變量分割和重命名；

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

第十步：重復(fù)第八步和第九步，直到完成所有滿足模型的變量分割與重命名，同時(shí)更新變量?jī)?nèi)存分配表；

第十一步：根據(jù)變量?jī)?nèi)存分配表、內(nèi)存塊操作表通過(guò)全局優(yōu)化模塊進(jìn)行內(nèi)存變量全局優(yōu)化分配；一種全局優(yōu)化的方法是采用遺傳算法計(jì)算出內(nèi)存分配的優(yōu)化解；根據(jù)算法所找到的最優(yōu)解更新變量?jī)?nèi)存分配表和內(nèi)存塊操作表；

第十二步：根據(jù)內(nèi)存塊操作表的信息中各個(gè)內(nèi)存塊操作的源和目的操作數(shù)的更新方式，結(jié)合第三步中的內(nèi)存操作結(jié)構(gòu)信息中描述的尋址模式，由尋址模式分配組件選擇合適的尋址模式；

第十三步：根據(jù)最終的變量?jī)?nèi)存分配表生成變量鏈接文件；

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