基于時(shí)序邏輯的編譯優(yōu)化測(cè)試用例生成方法

摘要：提出一種基于時(shí)序邏輯公式的關(guān)鍵節(jié)點(diǎn)控制圖生成方法，生成的測(cè)試用例針對(duì)性強(qiáng)，容易擴(kuò)展；并以該方法改進(jìn)了一種編譯優(yōu)化自動(dòng)化測(cè)試工具，在很大程度上消除了其測(cè)試冗余，提高了測(cè)試效率。

關(guān)鍵詞：編譯優(yōu)化； 測(cè)試用例； 時(shí)序邏輯； 基本塊； 關(guān)鍵節(jié)點(diǎn)控制圖

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)07－0046－03

0引言

編譯器是軟件開(kāi)發(fā)的基礎(chǔ)支撐工具，其正確性直接影響到應(yīng)用軟件的可靠性。它需要通過(guò)充分測(cè)試以保證其質(zhì)量。編譯器測(cè)試用例生成方法可以分為針對(duì)前端語(yǔ)法語(yǔ)義的用例生成方法和針對(duì)后端優(yōu)化算法的用例生成方法兩大類(lèi)[1]。

針對(duì)前端語(yǔ)法語(yǔ)義的測(cè)試用例生成方法的基本思想是基于語(yǔ)言文法生成測(cè)試用例，用于編譯器前端翻譯功能的測(cè)試[2，3]。隨著編譯技術(shù)的發(fā)展，優(yōu)化技術(shù)逐漸成為編譯技術(shù)研究的核心內(nèi)容，出現(xiàn)了一些針對(duì)后端優(yōu)化的測(cè)試用例生成方法，文獻(xiàn)[4]介紹一種針對(duì)編譯后端優(yōu)化的基于文法生成代碼的優(yōu)化測(cè)試用例生成方法。首先基于文法生成標(biāo)準(zhǔn)的源程序，再根據(jù)具體的優(yōu)化技術(shù)特點(diǎn)加入新的語(yǔ)句以滿(mǎn)足特定優(yōu)化條件。該方法仍屬于基于文法的用例生成方法，針對(duì)性較弱，具有較大局限性。文獻(xiàn)[5，6]對(duì)不同的優(yōu)化類(lèi)型進(jìn)行建模，再將模型映射到程序文本作為測(cè)試用例。此方法有較好的針對(duì)性，但其建模過(guò)程和模型映射過(guò)程需要對(duì)不同的優(yōu)化進(jìn)行不同的定制，實(shí)現(xiàn)較為復(fù)雜。由中國(guó)科學(xué)院軟件所研制的JTT是一個(gè)面向編譯優(yōu)化的自動(dòng)化測(cè)試工具，它用于嵌入式環(huán)境下的C++優(yōu)化編譯器的系統(tǒng)測(cè)試和回歸測(cè)試[7]。JTT在自動(dòng)生成程序控制結(jié)構(gòu)的基礎(chǔ)上，通過(guò)某些特定的隨機(jī)策略添加計(jì)算賦值語(yǔ)句，從而生成完整的測(cè)試用例。它缺乏對(duì)特定優(yōu)化精確的形式化描述，難以生成有針對(duì)性的優(yōu)化測(cè)試用例，存在大量測(cè)試冗余。文獻(xiàn)[8]使用基于時(shí)序邏輯的條件重寫(xiě)規(guī)則LHS→RHS ifΦ精確刻畫(huà)了編譯優(yōu)化。其中條件Φ用時(shí)序邏輯公式描述。

1基于時(shí)序邏輯的編譯優(yōu)化描述

典型的優(yōu)化變換能采用基于時(shí)序邏輯的條件重寫(xiě)規(guī)則LHS→RHS ifΦ來(lái)作精確刻畫(huà)[9]。變換由兩部分組成，即變換的一系列動(dòng)作和保證變換正確性的條件。變換動(dòng)作通過(guò)程序控制流圖中節(jié)點(diǎn)和連接邊的變化表示；有四種基本動(dòng)作，即節(jié)點(diǎn)替代(Replace)、邊刪除(Remove_edge)、邊添加(Add_edge)和邊分裂(Split_edge)。如圖1所示，節(jié)點(diǎn)替代是用一系列的節(jié)點(diǎn)替代控制流圖中的某個(gè)節(jié)點(diǎn)；刪除邊和添加邊分別是移除和添加控制流圖中的連接邊；分裂邊是在相連接的兩節(jié)點(diǎn)間插入中間節(jié)點(diǎn)。

3討論及應(yīng)用

上述算法分為兩個(gè)階段：公式規(guī)整化和節(jié)點(diǎn)生成。其中公式規(guī)整化階段將每個(gè)條件的公式轉(zhuǎn)換為標(biāo)準(zhǔn)形式，以便節(jié)點(diǎn)生成階段的處理；節(jié)點(diǎn)生成階段則生成關(guān)鍵節(jié)點(diǎn)及關(guān)鍵節(jié)點(diǎn)之間的控制流。該算法需要的內(nèi)存空間與公式中所涉及到的節(jié)點(diǎn)數(shù)量成正比，需要的時(shí)間與條件數(shù)目以及節(jié)點(diǎn)數(shù)目成正比。因此，算法一定可以在有限時(shí)間內(nèi)結(jié)束。

構(gòu)造出一個(gè)基本塊的關(guān)鍵節(jié)點(diǎn)控制圖后，可以此為模板很方便地生成大量有針對(duì)性的測(cè)試用例；可以使用隨機(jī)策略或啟發(fā)式策略，在關(guān)鍵節(jié)點(diǎn)控制圖的節(jié)點(diǎn)之間插入新的節(jié)點(diǎn)。插入的新節(jié)點(diǎn)需要滿(mǎn)足插入點(diǎn)之前緊鄰關(guān)鍵節(jié)點(diǎn)的前向?qū)傩裕残枰獫M(mǎn)足插入點(diǎn)之后緊鄰關(guān)鍵節(jié)點(diǎn)的后向?qū)傩浴＊?/p>

本文基于前面介紹的方法對(duì)JTT工具作了改進(jìn)，用腳本描述了基于CTL的編譯優(yōu)化刻畫(huà)公式，并在此基礎(chǔ)上利用關(guān)鍵節(jié)點(diǎn)控制圖生成算法生成了一個(gè)基本塊的關(guān)鍵控制結(jié)構(gòu)。對(duì)于圖中的每一條虛邊，使用隨機(jī)策略（可以指定生成代碼的并行程度及嵌套程度）生成實(shí)際路徑來(lái)代替[7]，插入賦值語(yǔ)句、表達(dá)式、變量和常量定義等語(yǔ)句，生成完整的源程序文件。通過(guò)改進(jìn)后，使得JTT測(cè)試用例更具針對(duì)性，縮短了測(cè)試時(shí)間，提高了測(cè)試效率。在工業(yè)界的實(shí)踐表明，改進(jìn)后的JTT能夠取得良好的測(cè)試質(zhì)量。圖5為JTT截圖。

4結(jié)束語(yǔ)

傳統(tǒng)的編譯優(yōu)化測(cè)試方法使用基于文法的方法生成測(cè)試用例，其針對(duì)性差、測(cè)試冗余較多。本文在文獻(xiàn)[8]使用時(shí)序邏輯公式精確刻畫(huà)編譯優(yōu)化方法的基礎(chǔ)上，提出一種面向編譯優(yōu)化的測(cè)試用例自動(dòng)生成方法，利用時(shí)序邏輯公式中出現(xiàn)的關(guān)鍵節(jié)點(diǎn)以及節(jié)點(diǎn)間的時(shí)序關(guān)系，構(gòu)造一個(gè)或多個(gè)滿(mǎn)足優(yōu)化條件的基本塊的關(guān)鍵節(jié)點(diǎn)及節(jié)點(diǎn)間的控制關(guān)系，并結(jié)合實(shí)例詳細(xì)描述了該方法。該方法生成的測(cè)試用例針對(duì)性強(qiáng)，適用于多種編譯優(yōu)化的測(cè)試。本文由此改進(jìn)了JTT，很大程度上消除了測(cè)試冗余，提高了測(cè)試效率。下一步工作將集中在生成更為豐富的控制結(jié)構(gòu)和數(shù)據(jù)流信息上。

參考文獻(xiàn)：

[1]BOUJARWAH A S， SALEH K. Compiler test case generation me－thods: a survey and assessment[J]. Information and Software Technology， 1997，39(9):617－625.

[2]PURDOM P. A sentence generator for testing parsers[J]. BIT Numerical Mathematics， 1972，12(3):366－375.

[3]JIANG Liyuan， HUANG Guangjun. An automatic system of generating test cases for compiler[J]. Journal of Northwestern Polytechnical University， 1992，10(2):153－158.

[4]BURGESS C J， SAIDI M. The automatic generation of test cases for optimizing Fortran compilers[J]. Information and Software Technology， 1996，38(2):111－119.

[5]KULIAMIN V V， PETRENKO A K. Applying model based testing in different contexts[EB/OL].2002(2004－12－28).http://www.ispras.ru/groups/rv/downloads/Dagstuhl2004_Kuliamin.pdf.

[6]KOSSATCHEV A， PETRENKO A， ZELENOV S， et al.Using model－based approach for automated testing of optimizing compilers: proc.of the International Workshop on Program Understanding[C]. Novosi－birsk， Russia:[s.n.]， 2003:81－88.

[7]朱丹楓.一種用于測(cè)試編譯優(yōu)化的程序控制結(jié)構(gòu)生成算法[D].北京:中國(guó)科學(xué)院軟件研究所，2005.

[8]LACEY D. Program transformation using temporal logic specification[D]. Oxford: Oxford University Computing Laboratory， 2003.

[9]CLARKE E M， EMERSON E A， SISTLA A P. Automatic verification of finite－state concurrent systems using temporal logic specifications[J]. ACM Transactions on Programming Languages and Systems， 1986，8(2):244－263.

[10]EMERSON E A， HALPERN J Y. Decision procedures and expressiveness in the temporal logic of branching time[J]. Journal of Computer and System Sciences， 1985，30(1):1－24.

[11]BEN ARI M， MANNA Z， PNUELI A. The temporal logic of bran－ching time[J]. Acta Information， 1983，20:207－226.

[12]KATOEN J P. Principles of model checking[EB/OL]. http://www.cs.auc.dk/~kgl/DAT4F02/KatoenIntro.ps.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”