[發(fā)明專利]基于代碼復(fù)制超級塊的程序執(zhí)行優(yōu)化方法

無效

• 申請?zhí)枺?/td>: 201010278538.0
• 申請日: 2010-09-11
• 公開（公告）號: CN101923481A
• 公開（公告）日: 2010-12-22
• 發(fā)明（設(shè)計(jì)）人: 管海兵;陳凱;鄧海鵬;劉博;張俊
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 上海交達(dá)專利事務(wù)所 31201
• 代理人: 王錫麟;王桂忠

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

本發(fā)明涉及的是一種計(jì)算機(jī)技術(shù)領(lǐng)域的方法，具體是一種二進(jìn)制系統(tǒng)中的基于代碼復(fù)制超級塊的程序執(zhí)行優(yōu)化方法。

背景技術(shù)

動態(tài)二進(jìn)制翻譯是虛擬執(zhí)行技術(shù)中應(yīng)用最為廣泛的方法，是為遺留代碼提供移植可能性和提高軟件的平臺適應(yīng)性的一種有效手段，它在不需要可執(zhí)行程序的源代碼的情況下，可以動態(tài)地將源機(jī)器平臺上的二進(jìn)制程序經(jīng)過轉(zhuǎn)換，運(yùn)行于其他目標(biāo)機(jī)器平臺上。對于動態(tài)二進(jìn)制翻譯器自身而言，執(zhí)行性能是一個(gè)非常重要的衡量指標(biāo)。所謂執(zhí)行性能是指，以源程序在原架構(gòu)下運(yùn)行的效率為參照，其在動態(tài)二進(jìn)制翻譯器提供的運(yùn)行環(huán)境下的效率損失度越低，翻譯器的執(zhí)行性能越好。

為了提高動態(tài)二進(jìn)制翻譯器的性能，動態(tài)翻譯器采用很多原本在編譯領(lǐng)域被廣泛采用的策略和方法，鑒于動態(tài)二進(jìn)制翻譯與編譯技術(shù)相比缺少源代碼資源的特性，所以也發(fā)展出來了動態(tài)二進(jìn)制領(lǐng)域所特有的優(yōu)化技術(shù)和方法。其中被廣泛采用的有超級塊生成技術(shù)、鏈接技術(shù)等。在動態(tài)二進(jìn)制領(lǐng)域，因?yàn)闆]有源代碼，對程序所進(jìn)行的優(yōu)化等所需要的大部分信息都是通過程序的剖分信息來獲取的。

一般來說，在動態(tài)二進(jìn)制領(lǐng)域，對源程序的翻譯，執(zhí)行，優(yōu)化等操作都是以源程序的基本塊為單位進(jìn)行的。所謂基本塊，是指僅有一個(gè)入口，并且以跳轉(zhuǎn)，返回等指令結(jié)束的一組指令序列。程序從基本塊的入口開始執(zhí)行，然后，最終在基本塊的出口跳出，并跳到另外一個(gè)基本塊的入口繼續(xù)執(zhí)行指令序列。程序的剖分信息的獲取就是以基本塊為單位進(jìn)行的，包括基本塊的執(zhí)行次數(shù)，跳轉(zhuǎn)地址等等一系列信息。所謂超級塊，根據(jù)已獲取的剖分信息，按一定的規(guī)則挑選指定的幾個(gè)基本塊序列重新組合，形成的更長的指令序列，用以提高程序的性能。它除了比基本塊長以外，還兼有多個(gè)出口的特性。

剖分信息的分類，主要有如下三種：

1、基于基本塊的信息收集，也就是基本塊運(yùn)行特性信息的收集，基本上局限于基本塊的運(yùn)行次數(shù)，和跳轉(zhuǎn)目標(biāo)塊等粗略信息。雖說它收集的信息較為粗略，但是，它給系統(tǒng)的開銷比較小，所以，它在性能要求比較高的動態(tài)的系統(tǒng)中應(yīng)用的比較多。

2、基于邊的信息收集，即，以一個(gè)基本塊以及隨后的基本塊組合而成的邊為基本的信息收集單位。基于邊的信息收集比基于塊的要豐富一些，也能更好的描述程序的行為特征。但是，隨之而來的也是對系統(tǒng)帶來的開銷也是比較大的。

3、基于路徑的信息收集。根據(jù)程序的控制流圖進(jìn)行，以單條執(zhí)行路徑為單位進(jìn)行信息收集。這樣的信息收集方式可以最接近程序真實(shí)的描述程序的行為特征。但是，它所付出的代價(jià)也是最大的.由于它龐大的系統(tǒng)開銷，在動態(tài)二進(jìn)制翻譯器中，基本上不被采用.

對于有中間語言的動態(tài)二進(jìn)制翻譯器來說，比如valgrind，UQDBT，構(gòu)造超級塊都傾向于在自身定義的中間語言，利用程序收集的信息，結(jié)合特定的算法進(jìn)行。然后，再集中放到后端翻譯成目標(biāo)代碼。一般的有中間語言的超級塊構(gòu)造方法流程如下：

1)利用上所述的三種種類信息收集方法，對信息進(jìn)行采集。一般來說，一個(gè)翻譯好的基本塊對應(yīng)有一個(gè)對象對它的信息進(jìn)行維護(hù)。通過上述的三種方法收集的信息一般來說是存放在各自的對象中。

2)當(dāng)滿足一定的條件，比如達(dá)到閾值等，程序就會觸發(fā)超級塊的構(gòu)造例程，因?yàn)橛兄虚g語言，所以，程序就先把一個(gè)一個(gè)的源程序基本塊經(jīng)過一定的處理，比如跳轉(zhuǎn)反轉(zhuǎn)等，按照一定的算法翻譯成一個(gè)大的中間語言程序塊，然后在翻譯成一個(gè)大的目標(biāo)程序塊，也就是超級塊。

3)最后就是程序跳到翻譯好的目標(biāo)程序超級塊進(jìn)行執(zhí)行。

經(jīng)對現(xiàn)有文獻(xiàn)檢索發(fā)現(xiàn)，中國專利文獻(xiàn)號CN101387970A，公開日2009-3-18，記載了一種“利用剖分信息生成超級塊的方法”，該技術(shù)詳細(xì)介紹了二進(jìn)制翻譯領(lǐng)域中Crossbit的構(gòu)造超級塊的一般流程。但是該技術(shù)有一個(gè)不容忽視的問題：在構(gòu)造超級塊的過程中，當(dāng)一個(gè)基本塊在多個(gè)超級塊中都是被需要時(shí)，勢必會造成除了只有一個(gè)被利用外，另外的超級塊都因?yàn)槿鄙佼?dāng)前塊而被中間截?cái)啵a(chǎn)生多個(gè)較短超級塊，或者基本塊碎片。

另經(jīng)檢索發(fā)現(xiàn)，中國專利文獻(xiàn)號CN101488096A，公開日2009-7-22，記載了一種“利用出入邊關(guān)系的部分信息構(gòu)建超級塊的方法”，該技術(shù)采用的是基于入邊和出邊的部分信息來構(gòu)造超級塊的方法，但是該方法在構(gòu)造超級塊的過程中容易產(chǎn)生重復(fù)，從而使得基本塊的數(shù)量龐大。

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

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的上述不足，提供一種基于代碼復(fù)制超級塊的程序執(zhí)行優(yōu)化方法，通過基本塊代碼復(fù)制來生成超級塊，使得基本塊的長度變長，基本塊的數(shù)量減少，從而提高生成的超級塊的質(zhì)量，且可移植性好。