[發(fā)明專利]匯編級(jí)跨文件調(diào)度框架的構(gòu)建方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310697997.6
• 申請(qǐng)日: 2013-12-18
• 公開(kāi)（公告）號(hào): CN103645930B
• 公開(kāi)（公告）日: 2017-03-08
• 發(fā)明（設(shè)計(jì)）人: 朱浩;彭楚;王東輝;洪纓
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院聲學(xué)研究所
• 主分類號(hào): G06F9/45
• 分類號(hào): G06F9/45;G06F9/46
• 代理公司: 北京億騰知識(shí)產(chǎn)權(quán)代理事務(wù)所11309
• 代理人: 陳霽

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)領(lǐng)域，尤其涉及一種匯編級(jí)跨文件調(diào)度框架的構(gòu)建方法。?

背景技術(shù)

編譯優(yōu)化的效果與編譯器可見(jiàn)的視野息息相關(guān)，更寬的視野能給編譯器更大的發(fā)揮空間，從而獲得更好的優(yōu)化效果。采用跨文件調(diào)度框架能使編譯器的視野擴(kuò)大至整個(gè)程序是未來(lái)編譯領(lǐng)域的發(fā)展方向。然而，跨文件調(diào)度框架下進(jìn)行的過(guò)程間分析、優(yōu)化等均占用了過(guò)多的編譯時(shí)間和較大的存儲(chǔ)空間，這就導(dǎo)致絕大多數(shù)編譯器并不支持跨文件調(diào)度框架。?

現(xiàn)有技術(shù)方案一般是針對(duì)編譯框架的中間語(yǔ)言提出，其中特征較為明顯的實(shí)現(xiàn)方法包括Vortex編譯器、SYZYGY編譯系統(tǒng)、LLVM編譯系統(tǒng)。其中：?

VorteX是華盛頓大學(xué)實(shí)現(xiàn)的支持跨文件優(yōu)化的編譯器。Vortex編譯器前端正常的處理整個(gè)應(yīng)用程序，然后利用它的專用中間語(yǔ)言Vortex?IL中間代碼表示把所有的編譯結(jié)果保存下來(lái)，一旦得到全部的過(guò)程的VIL表示，也就形成了跨文件調(diào)度框架。?

SYZYGY是HP公司的Sungdo?Moon等人于2004年實(shí)現(xiàn)的基于HP-UX的Itanium處理器的編譯器的連接時(shí)跨文件過(guò)程間優(yōu)化框架。它將傳統(tǒng)編譯流程劃分為四個(gè)階段，包括：前端、連接時(shí)、過(guò)程間分析和后端，它選擇來(lái)連接時(shí)來(lái)可見(jiàn)全部的過(guò)程信息，所以在連接前保存目標(biāo)代碼的編譯結(jié)果。?

LLVM是伊利諾斯大學(xué)2004年提出的連接時(shí)全程序優(yōu)化框架。為了支持全程序優(yōu)化，LLVM選擇的是通過(guò)一個(gè)偽連接器來(lái)保存編譯的中間結(jié)果，這個(gè)中間結(jié)果以目標(biāo)文件的面貌出現(xiàn)。但不同于SYZYGY的目標(biāo)代碼。LLVM擴(kuò)展?了GCC原編譯器的Link階段。在LLVM系統(tǒng)中提供了一個(gè)用于進(jìn)行跨文件過(guò)程間分析和優(yōu)化的偽連接器，這個(gè)連接器主要用來(lái)處理LLVM系統(tǒng)自身生成的目標(biāo)代碼和LLVM匯編代碼。LLVM修改了GCC前端，這個(gè)前端完成對(duì)源程序的處理生成樹(shù)表示后將樹(shù)表示轉(zhuǎn)換成LLVM的中間代碼表示形式，中級(jí)優(yōu)化器對(duì)這個(gè)中間代碼表示進(jìn)行一系列優(yōu)化后生成LLVM的.o文件。全部程序都被修改后的前端轉(zhuǎn)換為L(zhǎng)LVM的.o文件后，再調(diào)用LLVM的優(yōu)化連接器將它們Link為一個(gè)單獨(dú)的文件。這樣編譯器就可見(jiàn)到全部的過(guò)程并基于這個(gè)文件進(jìn)行跨文件的過(guò)程間分析和優(yōu)化變形。完成優(yōu)化變形后，這個(gè)LLVM中間代碼表示被轉(zhuǎn)換成GCC自身所使用的RTL表示。GCC編譯器處理RTL表示，生成真正的目標(biāo)代碼，然后調(diào)用真正的Nati?ve?Li?nker生成最終的可執(zhí)行文件。?

現(xiàn)有技術(shù)主要是通過(guò)保存編譯器的中間結(jié)果實(shí)現(xiàn)跨文件調(diào)度框架，而保存中間結(jié)果是為了輔助跨文件間過(guò)程調(diào)度，但這并不能提供合適的結(jié)構(gòu)去實(shí)現(xiàn)指令級(jí)再調(diào)度。?

發(fā)明內(nèi)容

本發(fā)明的目的是針對(duì)上述問(wèn)題，提供了一種有效的匯編級(jí)跨文件調(diào)度框架的構(gòu)建方法。?

為實(shí)現(xiàn)上述目的，本發(fā)明提供了一種匯編級(jí)跨文件調(diào)度框架的構(gòu)建方法,其包括以下步驟：?

構(gòu)建匯編級(jí)數(shù)據(jù)依賴圖ADDG，判斷、分析并描述匯編級(jí)寄存器內(nèi)指令之間的數(shù)據(jù)依賴關(guān)系，并且利用偽相關(guān)檢測(cè)算法進(jìn)行寄存器重新分配，避免臨時(shí)寄存器的復(fù)用帶來(lái)數(shù)據(jù)間的偽相關(guān)；以及?

構(gòu)建匯編級(jí)控制依賴圖ACFG，控制數(shù)據(jù)依賴分析，并添加控制依賴圖CDG中刪除冗余信息的特性來(lái)輔助后續(xù)調(diào)度，構(gòu)建基于多叉樹(shù)結(jié)構(gòu)的謂詞分析方法，通過(guò)遍歷控制流圖，跨基本塊的分析條件判斷相關(guān)指令間的數(shù)據(jù)依賴關(guān)系來(lái)完成謂詞分析；以及?

構(gòu)建匯編級(jí)程序調(diào)用圖APCG，組織管理全局源文件間的關(guān)系；?

所述APCG中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)所述ACFG，所述ACFG中每個(gè)節(jié)點(diǎn)可映射到一個(gè)匯編級(jí)基本塊，所述ACFG中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)獨(dú)立的ADDG。?

進(jìn)一步地,所述ADDG包括數(shù)據(jù)依賴檢測(cè)算法、ADDG創(chuàng)建算法以及所述偽相關(guān)檢測(cè)算法，其中，?

所述數(shù)據(jù)依賴檢測(cè)算法用于判斷兩條指令之間為何種所述數(shù)據(jù)依賴關(guān)系；?

所述ADDG創(chuàng)建算法反映了匯編級(jí)基本塊內(nèi)全部指令之間為何種所述數(shù)據(jù)依賴關(guān)系，并表現(xiàn)出來(lái)；?

所述偽相關(guān)檢測(cè)算法用于寄存器重新分配，避免偽相關(guān)帶來(lái)的數(shù)據(jù)依賴關(guān)系。?

進(jìn)一步地,所述ADDG是一個(gè)有向無(wú)環(huán)圖DAG。?

進(jìn)一步地,所述ACFG是一個(gè)有向有環(huán)圖DCG。?

進(jìn)一步地,所述構(gòu)建基于多叉樹(shù)結(jié)構(gòu)的謂詞分析方法是通過(guò)遍歷控制流圖，跨基本塊的分析條件判斷相關(guān)指令之間的數(shù)據(jù)依賴關(guān)系來(lái)完成謂詞分析。?

進(jìn)一步地,所述寄存器重新分配包括以下步驟：?