[發(fā)明專(zhuān)利]一種基于代數(shù)系統(tǒng)的跨文件過(guò)程間優(yōu)化方法

有效

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

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

本發(fā)明涉及編譯器技術(shù)，尤其涉及一種基于代數(shù)系統(tǒng)的跨文件過(guò)程間優(yōu)化方法。

背景技術(shù)

函數(shù)棧框架在傳統(tǒng)編譯框架中是一種通用協(xié)議，并交由用戶(hù)在二進(jìn)制接口（Application?Binary?Interface,ABI）進(jìn)行定義。函數(shù)棧框架在處理函數(shù)調(diào)用時(shí)，它根據(jù)目標(biāo)機(jī)的硬件資源約束，盡可能的將臨時(shí)變量保存在臨時(shí)寄存器內(nèi)，而溢出部分則在函數(shù)體前被執(zhí)行前壓入棧內(nèi)，并通過(guò)存儲(chǔ)訪問(wèn)指令進(jìn)行棧操作，待函數(shù)體被執(zhí)行完后再逐一釋放函數(shù)棧內(nèi)的數(shù)據(jù)。

在這種模式下，由于目標(biāo)機(jī)器支持的最大寄存器數(shù)有限，而局部臨時(shí)變量由于生命周期而分布于多個(gè)基本塊內(nèi)，頻繁的入棧、出棧以及局部臨時(shí)寄存器復(fù)用將直接導(dǎo)致函數(shù)棧操作存在冗余。

現(xiàn)有技術(shù)主要是基于編譯框架下的中間語(yǔ)言進(jìn)行優(yōu)化，它主要面臨以下幾個(gè)主要問(wèn)題：1、函數(shù)棧框架協(xié)議的制定與目標(biāo)機(jī)器直接相關(guān)，修改時(shí)涉及的代碼量十分龐大，這將導(dǎo)致工作量急增；2、制定一種適合各種應(yīng)用場(chǎng)景的函數(shù)棧框架十分復(fù)雜，它牽涉到寄存器分配等多個(gè)階段，而且中間語(yǔ)言只是一種抽象語(yǔ)言，它并不能直接、有效的描述棧操作，因此，從中間語(yǔ)言入手進(jìn)行優(yōu)化的設(shè)計(jì)復(fù)雜度很高。

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

本發(fā)明的目的是為了解決上述現(xiàn)有技術(shù)存在的不足之處，提出一種基于代數(shù)系統(tǒng)的跨文件過(guò)程間優(yōu)化方法，它通過(guò)定義代數(shù)系統(tǒng)來(lái)對(duì)函數(shù)棧操作進(jìn)行針對(duì)性的優(yōu)化，并取得了更好的效果。

為實(shí)現(xiàn)上述目的，本發(fā)明提供了一種基于代數(shù)系統(tǒng)的跨文件過(guò)程間優(yōu)化方法，該方法包括以下步驟：

針對(duì)目標(biāo)機(jī)特征，選擇出涉及棧操作、邏輯運(yùn)算類(lèi)等指令，構(gòu)建代數(shù)系統(tǒng)，并為這些指令與代數(shù)系統(tǒng)建立映射關(guān)系；

從程序入口處開(kāi)始遍歷函數(shù)調(diào)用圖（Procedure?Call?Graph，PCG），判斷存在邊相連的節(jié)點(diǎn)是否分屬不同的源文件，如果是，繼續(xù)下一步操作，否則繼續(xù)遍歷PCG；

從函數(shù)調(diào)用指令開(kāi)始逆向沿著當(dāng)前函數(shù)內(nèi)的控制流圖（Control?Flow?Graph，CFG）開(kāi)始遍歷數(shù)據(jù)依賴(lài)圖（Data?Dependence?Graph，DDG），生成指令壓棧操作的代數(shù)表達(dá)式，并進(jìn)行代數(shù)表達(dá)式歸約；

分析后繼節(jié)點(diǎn)函數(shù)的出棧操作從中讀出常量值，并依次傳遞，優(yōu)化并計(jì)算，最終刪除冗余指令片段。

本發(fā)明定義一套粗糙的代數(shù)系統(tǒng)，通過(guò)棧操作生命周期分析將棧相關(guān)指令轉(zhuǎn)義為代數(shù)表達(dá)式，并最終形成λ表達(dá)式，通過(guò)迭代歸約λ表達(dá)式，有效地合并、釋放了函數(shù)棧框架中可優(yōu)化部分。除此之外，本發(fā)明在跨文件過(guò)程間優(yōu)化、常量傳播以及常量計(jì)算中也取得了較佳效果。

附圖說(shuō)明

圖1為棧操作生命周期分析流程示意圖；

圖2為函數(shù)棧框架優(yōu)化流程示意圖；

圖3為圖2所示函數(shù)棧框架優(yōu)化實(shí)例；

圖4為本發(fā)明實(shí)施例提供的一種基于代數(shù)系統(tǒng)的跨文件過(guò)程間優(yōu)化方法流程圖。

具體實(shí)施方式

下面通過(guò)附圖和實(shí)施例，對(duì)本發(fā)明的技術(shù)方案做進(jìn)一步的詳細(xì)描述。

線性空間中的代數(shù)系統(tǒng)由非空集合S及定義于集合S上的代數(shù)符集，關(guān)系集組成，代數(shù)系統(tǒng)中用于推理計(jì)算的代數(shù)表達(dá)式則是由常數(shù)、變量、有限個(gè)相關(guān)代數(shù)操作(加法、減法、乘法等)構(gòu)成。匯編函數(shù)內(nèi)的執(zhí)行路徑可看作是由多個(gè)匯編級(jí)基本塊組成有序多元組，假設(shè)存在一條執(zhí)行路徑L=<x1,x2,x3,..,xn>,其中L[i]=xi{i=1,…,n為執(zhí)行節(jié)點(diǎn)或沿路上的匯編級(jí)基本塊}，針對(duì)L的特征可定義函數(shù)：

對(duì)于一個(gè)確定的輸入L[i]而言，Ret(L[i])的值是可確定，那么L的執(zhí)行信息可被遞歸形式的跳轉(zhuǎn)函數(shù)Jump(L[i])=(if?Ret(L[i])=Ret1&&i≠n-1)thenSuccessor(L[i])else?if(i=n-1)then?Last(L[i])else?Jump(L[i-α])來(lái)表示，其中α(α>0)為路徑的回溯距離，Successor(L[i])=L[i+1]，Last(L[i])=L[n-1]。