周國昌,巨　艇,賴曉玲,朱　啟,王向濤,于登云,郭陽明

(1.中國空間技術(shù)研究院 西安分院,西安 710100;2.西北工業(yè)大學(xué) 計算機(jī)學(xué)院,西安 710072;3.中國航天科技集團(tuán)公司 科技委,北京100048)

?

信息科學(xué)與工程

DSP匯編程序基本塊劃分與優(yōu)化及其軟件實現(xiàn)

周國昌1,巨艇1,賴曉玲1,朱啟1,王向濤2,于登云3,郭陽明2

(1.中國空間技術(shù)研究院 西安分院,西安 710100;2.西北工業(yè)大學(xué) 計算機(jī)學(xué)院,西安 710072;3.中國航天科技集團(tuán)公司 科技委,北京100048)

摘要：針對空間環(huán)境中DSP軟錯誤檢測的需求，研究一種DSP匯編程序基本塊劃分與優(yōu)化方法，并對其進(jìn)行了軟件實現(xiàn)。該方法首先將匯編程序精簡為只含指令和標(biāo)號的“偽匯編”程序；再對“偽匯編”代碼進(jìn)行基本塊劃分；然后經(jīng)過3種優(yōu)化得到優(yōu)化后的基本塊。最后根據(jù)優(yōu)化前后的基本塊信息，分別繪制優(yōu)化前后的跳轉(zhuǎn)流程圖。利用該軟件可以將程序劃分為基本塊的集合，并提取每個基本塊的結(jié)構(gòu)信息，可有效支撐基于完整性檢查的程序流錯誤檢測。軟件代碼精簡、穩(wěn)定性好、空間復(fù)雜度小，對DSP單粒子效應(yīng)故障檢測有著重要的應(yīng)用價值。

關(guān)鍵詞：基本塊劃分；基本塊優(yōu)化；匯編程序；DSP

隨著空間技術(shù)的發(fā)展，基于高性能DSP的信息處理系統(tǒng)越來越多地被應(yīng)用于航天器平臺上。宇宙空間輻照環(huán)境中，DSP無時無刻不發(fā)生著對航天器有嚴(yán)重影響的單粒子效應(yīng)(SEE)，包括SEU(單粒子翻轉(zhuǎn))、SET(單粒子瞬態(tài)脈沖)、SEB(單粒子燒毀)、SEL(單粒子閉鎖)等，極大地降低了航天器運行的可靠性。因此，必須采取有效的措施，進(jìn)行單粒子效應(yīng)主動防護(hù)或選擇合理的檢測點完成單粒子軟錯誤故障的檢測與恢復(fù)[1-5]。 基于DSP的空間電子系統(tǒng)單粒子軟錯誤最主要的表現(xiàn)形式是控制流錯誤[6-8]?？刂屏麇e誤是指程序偏離了正確的執(zhí)行流程，導(dǎo)致程序輸出結(jié)果錯誤，甚至導(dǎo)致系統(tǒng)崩潰[8-10]。常見的控制流錯誤檢測方法是基于簽名監(jiān)測的方法[11-12]，即將程序劃分為若干個基本塊并為每個基本塊分配一個靜態(tài)簽名，在程序運行時再為每個基本塊計算動態(tài)簽名，然后通過比較靜態(tài)簽名與動態(tài)簽名的一致性來判斷程序是否發(fā)生控制流錯誤。該方法中簽名的生成方式具有很大的平臺依賴性，即在不同的指令集平臺上需采用不同的簽名生成方式，這在很大程度上限制了基于簽名的控制流錯誤檢測方法的可移植性。另一種控制流錯誤檢測方法是基于完整性檢查的控制流錯誤檢測方法[11,13-14]，該方法也是將程序劃分為基本塊的集合，然后通過檢查每個基本塊的執(zhí)行完整性來判斷程序是否發(fā)生控制流錯誤。執(zhí)行完整性檢查的依據(jù)是每個基本塊的結(jié)構(gòu)信息，如基本塊出口地址、基本塊入口地址、基本塊長度等。為此，需要在劃分基本塊時記錄下基本塊的結(jié)構(gòu)信息，以便在程序運行時將這些信息作為檢查基本塊是否被完整執(zhí)行的依據(jù)。 為此，本文基于完整性檢查方法思想，結(jié)合TI TMS320C6x系列DSP匯編程序的特點，提出了一種基本塊劃分與優(yōu)化方法，并對其進(jìn)行了軟件實現(xiàn)。利用該軟件可以將程序劃分為基本塊的集合，并提取每個基本塊的結(jié)構(gòu)信息，以支撐控制流錯誤的檢測。該軟件代碼精簡、穩(wěn)定性好、空間復(fù)雜度小，對DSP單粒子效應(yīng)故障檢測有著重要的應(yīng)用價值。

1　DSP匯編程序基本塊劃分與優(yōu)化方法

1.1基本塊劃分原理

基本塊是指一段順序執(zhí)行的代碼。DSP程序在其指令順序執(zhí)行的一段基本塊中，如果沒有發(fā)生控制流錯誤，程序?qū)⒅荒軓拇a的第一句進(jìn)入基本塊，從最后一句退出基本塊。即在正常情況下，基本塊中除最后一句外不應(yīng)出現(xiàn)控制流分支的情況；基本塊中除第一句外不應(yīng)出現(xiàn)控制流進(jìn)入的情況。 因此，分支指令出錯是導(dǎo)致控制流錯誤的主要原因。在劃分基本塊后，所有的分支指令都位于基本塊的末尾。當(dāng)出現(xiàn)分支指令錯誤時，控制流可能轉(zhuǎn)移到不正確的地址處開始執(zhí)行，也可能導(dǎo)致一個本該發(fā)生的控制流轉(zhuǎn)移沒有發(fā)生或相反。此外，DSP的軟錯誤也可能引起存儲單元中的信息發(fā)生單粒子翻轉(zhuǎn)，如果這種單粒子翻轉(zhuǎn)發(fā)生在程序存儲區(qū)，則有可能改變指令的編碼。實際分析表明，發(fā)生在程序存儲區(qū)的單粒子翻轉(zhuǎn)可能導(dǎo)致一條非分支指令轉(zhuǎn)變?yōu)榉种е噶睿灰部赡軐?dǎo)致一條分支指令轉(zhuǎn)變?yōu)榉欠种е噶?。此時，程序必然出現(xiàn)控制流錯誤。 針對DSP匯編程序劃分基本塊，就是在DSP匯編程序代碼中尋找程序控制指令，并以此確定基本塊的邊界。雖然不同平臺采用的指令集不同，但不同的分支指令集內(nèi)部都有用于實現(xiàn)函數(shù)調(diào)用、函數(shù)返回和跳轉(zhuǎn)的指令。因此，本文將以函數(shù)調(diào)用指令、函數(shù)返回指令和不含嵌套執(zhí)行的for循環(huán)指令等分支跳轉(zhuǎn)指令的位置為原始檢測點，進(jìn)行基本塊的劃分與優(yōu)化。

1.2基本塊劃分與優(yōu)化方法

在匯編語言一級，實現(xiàn)基本塊劃分的關(guān)鍵是識別函數(shù)調(diào)用指令、函數(shù)返回指令和不含嵌套執(zhí)行的for循環(huán)指令，以及以上分支跳轉(zhuǎn)指令的目的地址?；緣K劃分規(guī)則描述如下：(1)跳轉(zhuǎn)語句和函數(shù)調(diào)用作為一個基本模塊的出口；(2)當(dāng)前跳轉(zhuǎn)(調(diào)用)的后一句作為基本模塊的入口；(3)當(dāng)前跳轉(zhuǎn)(調(diào)用)的目的語句作為基本模塊的入口；(4)當(dāng)前跳轉(zhuǎn)(調(diào)用)的目的語句的前一句作為基本模塊的出口。 本文提出的控制流檢測思想是檢測基本塊的執(zhí)行完整性，即通過檢查每個基本塊是否被完整執(zhí)行來檢查程序是否發(fā)生控制流錯誤。完整性檢查的核心就是在被檢測模塊的出口處檢查當(dāng)前模塊的指令執(zhí)行條數(shù)和模塊最后一條語句的邏輯地址是否和劃分基本塊時記錄的一致。在這種檢測機(jī)制下，由于函數(shù)返回和函數(shù)調(diào)用在控制流意義上都是無分支的，可以考慮將兩個在控制流上無分支的基本塊的執(zhí)行完整性合并起來檢查。為此，本文提出了“返回優(yōu)化”和“調(diào)用優(yōu)化”兩種優(yōu)化機(jī)制。即函數(shù)調(diào)用發(fā)生時，控制流一定會從調(diào)用基本塊轉(zhuǎn)移到子函數(shù)的第一個基本塊。如果在這個過程從沒有發(fā)生控制流錯誤，在子函數(shù)第一個基本塊的檢測點處，執(zhí)行的指令條數(shù)一定等于調(diào)用基本塊的指令條數(shù)加上子函數(shù)第一塊的指令條數(shù)，塊出口邏輯地址一定為子函數(shù)調(diào)用塊的出口指令的邏輯地址，這2個確定的信息就作為軟錯誤檢測的依據(jù)，其參考值已經(jīng)在程序執(zhí)行前記錄在分塊表中。

此外，對于不含嵌套執(zhí)行的for循環(huán)，循環(huán)體執(zhí)行完之后控制流一定會進(jìn)入其后的一個基本塊，此時則可以進(jìn)行“循環(huán)優(yōu)化”。對于for循環(huán)，其循環(huán)次數(shù)是已知的。也就是說，可以計算出循環(huán)體總共執(zhí)行的指令條數(shù)。即，對于不嵌套的for循環(huán)，能夠在循環(huán)體之后的一個基本塊出口處確切地知道在2個基本塊之間總共執(zhí)行了多少條指令以及控制流應(yīng)在的確切位置，有了這2個信息，就可以將不嵌套的for循環(huán)的循環(huán)體和其后的一個基本塊的完整性合并起來檢測，從而減少檢測點的數(shù)量，減少檢測開銷。

1.3優(yōu)化效果分析

本文提出的基本塊優(yōu)化措施，主要應(yīng)用于DSP匯編程序的函數(shù)調(diào)用、函數(shù)返回和不含嵌套執(zhí)行的for循環(huán)，優(yōu)化措施的效果實際上與程序的性質(zhì)有關(guān)，即程序中出現(xiàn)函數(shù)調(diào)用的次數(shù)和循環(huán)操作的出現(xiàn)頻率對優(yōu)化的性能具有很大的影響。 函數(shù)調(diào)用和函數(shù)返回是成對出現(xiàn)的，即程序中每出現(xiàn)一個子函數(shù)調(diào)用，就可以在檢測點優(yōu)化時減少2個檢測點。而程序中大多數(shù)循環(huán)也都能用采用上述優(yōu)化措施進(jìn)行優(yōu)化。在典型的FFT程序上，優(yōu)化措施使優(yōu)化后的檢測點數(shù)量降到優(yōu)化前的60%左右。對于一般的DSP程序而言，優(yōu)化措施能使檢測點的數(shù)量降到優(yōu)化前的70%以下。

2　軟件的設(shè)計

2.1軟件的功能設(shè)計

本軟件基于完整性檢查方法，以TI TMS320C6x系列DSP匯編程序為對象，設(shè)計實現(xiàn)一個能夠?qū)崿F(xiàn)基本塊劃分和優(yōu)化方法的軟件工具。

匯編級的DSP基本塊劃分和優(yōu)化根據(jù)基本塊的標(biāo)識信息，執(zhí)行基本塊的初始劃分、函數(shù)返回優(yōu)化、函數(shù)調(diào)用優(yōu)化和循環(huán)優(yōu)化等步驟。軟件的執(zhí)行過程如圖1所示。

圖1　軟件的執(zhí)行流程圖

基于以上基本塊的劃分規(guī)則和圖1，DSP匯編程序基本塊的劃分與優(yōu)化軟件應(yīng)包括如下功能：

(1)DSP匯編代碼的簡化預(yù)處理

目前，TI公司為旗下的TI C6x系列DSP提供了集成開發(fā)環(huán)境CCS(Code Composer Studio)。缺省條件下，可以在CCS編譯器工作目錄下找到DSP工程的匯編語言程序。但該匯編程序包含的變量聲明、函數(shù)聲明、標(biāo)號說明等信息對于基本塊劃分來說是不必要的，而且會對基本塊的劃分工作帶來很大干擾。此外，編譯得到的匯編程序中，并不包含匯編指令的地址信息。因此，本軟件工具將對其進(jìn)行簡化預(yù)處理，去除掉無用的信息，同時填入偽邏輯地址(行號)，以方便基本塊的劃分。

(2)劃分基本塊并生成分塊表

根據(jù)基本塊的關(guān)鍵字將匯編程序劃分為若干個基本塊的集合，并將每個基本塊的結(jié)構(gòu)信息寫入分塊表中。此處，基本塊關(guān)鍵字指在匯編語言中的跳轉(zhuǎn)指令、函數(shù)調(diào)用指令和函數(shù)返回指令，分塊表則為一個鏈表，用于保存基本塊的結(jié)構(gòu)信息，包括基本塊入口、基本塊出口、基本塊長度、標(biāo)志字段、下一跳轉(zhuǎn)目的地址等信息。

(3)基本塊的函數(shù)返回優(yōu)化

根據(jù)每個基本塊的標(biāo)識信息，遍歷原始分塊表，找出函數(shù)返回指令所在基本塊對應(yīng)的結(jié)點，將此結(jié)點中的信息“合并”到函數(shù)調(diào)用返回后的基本塊所對應(yīng)的結(jié)點中，構(gòu)成新的基本塊和結(jié)點，形成函數(shù)返回優(yōu)化后的分塊表及其鏈接關(guān)系。

(4)基本塊的函數(shù)調(diào)用優(yōu)化

根據(jù)函數(shù)返回優(yōu)化后的基本塊的標(biāo)識信息，遍歷函數(shù)返回優(yōu)化后的分塊表，找出函數(shù)調(diào)用指令所在基本塊對應(yīng)的結(jié)點，將此結(jié)點中的信息“合并”到子函數(shù)的第一個基本塊所在的結(jié)點中，構(gòu)成新的基本塊和結(jié)點，形成函數(shù)返回優(yōu)化和函數(shù)調(diào)用優(yōu)化后的分塊表及其鏈接關(guān)系。

(5)基本塊的循環(huán)優(yōu)化

根據(jù)函數(shù)返回優(yōu)化和函數(shù)調(diào)用優(yōu)化后的基本塊的標(biāo)識信息，遍歷函數(shù)返回優(yōu)化和函數(shù)調(diào)用優(yōu)化后的分塊表，找出單重for循環(huán)的循環(huán)體所在基本塊對應(yīng)的結(jié)點，將此結(jié)點中的信息“合并”到循環(huán)體后基本塊所在的結(jié)點中，構(gòu)成新的分塊表和結(jié)點。

2.2軟件的主要算法

(1)簡化預(yù)處理算法

軟件工具可將CCS開發(fā)環(huán)境編譯得到的源匯編語言程序作為輸入，通過簡化預(yù)處理進(jìn)而輸出適合掃描分支跳轉(zhuǎn)指令的偽匯編代碼。

通過以上討論可知，簡化預(yù)處理算法主要用于識別匯編程序中的匯編指令，并將它們輸出到一個新的文本文件中，同時順序為每條匯編指令分配一個偽邏輯地址。即在順序掃描源匯編程序的過程中，若識別到“·”、“；”、“$”等開頭且獨占一行的代碼，則直接忽略而不做任何處理。

此外，編譯器將源程序編譯成匯編程序的過程中生成的很多標(biāo)號，往往標(biāo)志著跳轉(zhuǎn)指令的目的地址或函數(shù)調(diào)用中子函數(shù)的地址。在匯編程序首部，會對本程序中出現(xiàn)的所有標(biāo)號進(jìn)行集中說明，這部分信息對于基本塊劃分而言是可以忽略的。但是，在匯編程序內(nèi)部，每一個標(biāo)號都標(biāo)志著一個基本塊的開始，這些標(biāo)號對于基本塊劃分而言卻是必不可少的，必須保留下來。從程序運行的角度來看，標(biāo)號自身并不是一條可執(zhí)行的指令。所以，在簡化預(yù)處理階段不為標(biāo)號分配偽邏輯地址。

綜上所述，簡化預(yù)處理程序算法偽代碼描述如下：

輸入:匯編語言源程序輸出:只含標(biāo)號和指令的偽程序Step1:從源匯編程序中讀取一行,并判斷該行第一個非空字符的性質(zhì);Step2:如果第一個字符為“·”,表明該行內(nèi)容為聲明信息,回到第一步開始執(zhí)行;Step3:如果第一個字符為“;”,表明該行內(nèi)容為解釋信息,回到第一步開始執(zhí)行;Step4:如果第一個字符為“$”,表明該行內(nèi)容為一個標(biāo)號,將此行標(biāo)號輸出到文本文件中?；氐降谝徊介_始執(zhí)行。Step5:如果第二、三、四步的條件都不滿足,表明該行內(nèi)容為一條匯編指令,將該行輸出到文本文件中,并分配一個行號。回到第一步開始執(zhí)行。

(2)基本塊劃分算法

在基于TI C67xx的匯編程序中，分支跳轉(zhuǎn)指令的目的地址是用標(biāo)號來表示。在劃分基本塊的過程中，為了正確地表示基本塊的入口信息，應(yīng)先為匯編程序建立一個標(biāo)號表，完成標(biāo)號與“行號”的映射。此外， 在劃分基本塊時，在劃分基本塊的過程中，存在基本塊拆分的情況。當(dāng)原有的一個基本塊拆分成2個基本塊時，需要在分塊表中插入一個數(shù)據(jù)項，由數(shù)據(jù)結(jié)構(gòu)的知識可知，在順序表中插入一個結(jié)點需要大量的移動數(shù)據(jù)的操作，但在鏈表中插入一個結(jié)點只需要修改幾個指針即可。同時，在基本塊的優(yōu)化過程中，需要不斷地合并基本塊，每合并一個基本塊就應(yīng)該刪除其在表上的數(shù)據(jù)項，在鏈表上刪除一個結(jié)點也是很方便的。因此，需要構(gòu)造相應(yīng)的“分塊表”以及“暫存表”來保存劃分出的基本塊的信息和匯編偽代碼順序掃描過程中的輔助性信息。考慮到鏈表在數(shù)據(jù)插入和刪除上相對于順序表的優(yōu)勢，故本文將“分塊表”以及“暫存表”構(gòu)造成鏈表的形式。

在劃分基本塊的過程中，識別匯編指令是否為跳轉(zhuǎn)指令并將每一條指令的偽邏輯地址和暫存表的表項做比較，由此來確定基本塊的邊界。劃分基本塊的算法偽代碼描述如下：

Step1:從偽程序中讀取一行;Step2:判斷該行的行號是否與暫存表中的任一表項相匹配:if匹配(找到一個基本塊的入口,把其上一條指令作為上一基本塊的出口)Step2.1:把上一條語句作為上一個基本塊的出口,完善對應(yīng)的分塊表結(jié)點信息;Step2.2:在分塊表中新開一個結(jié)點,記錄當(dāng)前基本塊塊的入口信息;Step2.3:在暫存表中刪除表項與行號匹配的結(jié)點(轉(zhuǎn)到Step3);else不匹配(轉(zhuǎn)到Step3);Step3:判斷該行指令是否為跳轉(zhuǎn)指令或子函數(shù)調(diào)用指令。if是(找到一個基本塊的出口)Step3.1:在分塊表中完善前一個基本的信息,Step3.2:并在分塊表中新開一個結(jié)點,存儲下一個基本塊的信息;Step3.2:根據(jù)跳轉(zhuǎn)指令或子函數(shù)調(diào)用指令中的標(biāo)號信息查找標(biāo)號表中標(biāo)號對應(yīng)的行號,并在暫存表中新開一個結(jié)點來存儲這個行號信息;回到step1開始執(zhí)行。Else不是跳轉(zhuǎn)或調(diào)用指令(回到Step1開始執(zhí)行)。

(3)基本塊優(yōu)化算法

1)返回優(yōu)化算法和調(diào)用優(yōu)化算法在程序運行過程中，經(jīng)常會發(fā)生函數(shù)調(diào)用的情況。發(fā)生函數(shù)調(diào)用時，控制流會從主函數(shù)轉(zhuǎn)移到子函數(shù)上運行，在子函數(shù)執(zhí)行完之后，控制流又回到主函數(shù)上運行。事實上，控制流從子函數(shù)返回主函數(shù)是一個無分支的過程。此外，函數(shù)的調(diào)用過程也是一個控制流的無分支轉(zhuǎn)移過程，其優(yōu)化就是鏈表結(jié)點的合并過程。在調(diào)用優(yōu)化的基本塊合并時，并不會把調(diào)用指令所在的基本塊結(jié)點中的標(biāo)志信息保存下來，即調(diào)用優(yōu)化后，再也無法在分塊表中識別出這個函數(shù)調(diào)用。但是，對于返回優(yōu)化而言，必須先找到子函數(shù)調(diào)用，才能找到相應(yīng)的函數(shù)返回，才能進(jìn)行優(yōu)化。因此，返回優(yōu)化必須在調(diào)用優(yōu)化之前進(jìn)行。

此時，返回優(yōu)化算法偽代碼描述如下：

Step1:在分塊表中尋找main函數(shù)的入口所在的結(jié)點并讀取結(jié)點中的信息;Step2:根據(jù)結(jié)點標(biāo)志字段的信息判斷:Step2.1:若標(biāo)志字段為2,表明找到一個函數(shù)調(diào)用,則用一個堆棧S來保存當(dāng)前結(jié)點的下一個結(jié)點的地址,并根據(jù)當(dāng)前結(jié)點中的下一跳地址去尋找子函數(shù)所在的第一個結(jié)點,讀取子函數(shù)的第一個結(jié)點的信息。Step2.2:若標(biāo)志字段不為2,則讀取鏈表的下一個結(jié)點信息,回到Step2繼續(xù)執(zhí)行。Step3:讀取step2.1中找到的子函數(shù)第一個結(jié)點中的信息并根據(jù)結(jié)點標(biāo)志信息做判斷:Step3.1:若標(biāo)志字段為2,則表明子函數(shù)中存在有嵌套的函數(shù)調(diào)用,優(yōu)化程序回到Step2.1處重新執(zhí)行;Step3.2:若標(biāo)志字段為0,表明找到當(dāng)前子函數(shù)的最后一個基本塊。此時,優(yōu)化程序?qū)⒂诋?dāng)前基本塊和堆棧頂指向的基本塊合并起來。Step3.2.1:將當(dāng)前基本塊中的塊入口信息填入棧頂指向的基本塊相應(yīng)字段中,即用當(dāng)前塊的入口信息作為合并后的基本塊的入口信息。Step3.2.2:將當(dāng)前基本塊的長度信息和棧頂指向的基本塊的長度信息相加后填入棧頂指向的基本塊的相應(yīng)字段中,即更新優(yōu)化后基本塊的長度。Step3.2.3:釋放當(dāng)前結(jié)點,并維護(hù)鏈表的完整性。Step3.2.4:讀取棧頂指向的結(jié)點,然后彈出棧頂信息,回到Step2執(zhí)行。Step3.3:若標(biāo)志字段為1或3,則回到step3繼續(xù)執(zhí)行。

調(diào)用優(yōu)化的算法偽代碼描述如下：

Step1:在分塊表中尋找main函數(shù)的入口所在的結(jié)點,并讀取該結(jié)點信息;Step2:根據(jù)結(jié)點標(biāo)志字段的信息判斷:Step2.1:若結(jié)點標(biāo)志為2,表明找到一個函數(shù)調(diào)用:Step2.1.1:根據(jù)當(dāng)前結(jié)點的下一跳字段的信息尋找子函數(shù)的第一個基本塊所在的結(jié)點,將找到的結(jié)點記作N;Step2.1.2:將當(dāng)前結(jié)點的入口信息填入N結(jié)點的相應(yīng)字段中;將當(dāng)前結(jié)點的塊長信息和N結(jié)點中的塊長信息相加后填入N結(jié)點的塊長度字段中;Step2.1.3:刪除當(dāng)前結(jié)點,進(jìn)行鏈表完整性維護(hù)。Step2.1.4:從結(jié)點N處重新開始順序讀取鏈表結(jié)點信息,回到Step2開始執(zhí)行。Step2.2:若結(jié)點標(biāo)志不為2,則回到step2繼續(xù)執(zhí)行。

2)循環(huán)優(yōu)化

DSP程序中的for循環(huán)等對應(yīng)著大量的矩陣操作。實現(xiàn)矩陣操作的循環(huán)有一個共同的特點，即循環(huán)的次數(shù)是一定的。對于模塊的完整性檢查而言，在基本塊的檢測點處必須知道從上一個檢測點到當(dāng)前檢測點之間，程序執(zhí)行了多少條指令。當(dāng)循環(huán)的次數(shù)確定后，就能計算出這個循環(huán)總共需要執(zhí)行的指令數(shù)。為此，可以考慮將循環(huán)看作一個整體，即把循環(huán)當(dāng)作一個“基本塊”。

根據(jù)DSP程序中循環(huán)的結(jié)構(gòu)特征，循環(huán)優(yōu)化算法的偽代碼描述如下：

Step1:從分塊表的第一個結(jié)點開始,讀取結(jié)點的信息;Step2:根據(jù)當(dāng)前結(jié)點中的信息判斷,是否當(dāng)前結(jié)點中下一跳地址等于塊入口地址:Step2.1:若是,表明找到一個可以優(yōu)化的循環(huán),開始進(jìn)行循環(huán)優(yōu)化:Step2.1.1:將當(dāng)前結(jié)點的塊入口信息填入鏈表下一個結(jié)點的塊入口信息中;Step2.1.2:計算循環(huán)塊的總體長度,并和下一個結(jié)點的塊長度值相加后填入下一結(jié)點的塊長度字段中;Step2.1.3:刪除當(dāng)前結(jié)點,進(jìn)行鏈表完整性維護(hù);Step2.1.4:讀取鏈表的下一結(jié)點,回到Step2,繼續(xù)執(zhí)行。Step2.2:若不是,讀取鏈表的下一結(jié)點,回到Step2,繼續(xù)執(zhí)行。

3　軟件的實現(xiàn)與運行

基于圖1所示的執(zhí)行流程，軟件選擇在Visual Studio 2008下基于MFC的對話框(Dialog)進(jìn)行開發(fā)，界面設(shè)計為2個窗口，一個是用來顯示代碼及分塊信息的基本窗口，另一個是專用于顯示控制流程圖的作圖窗口?；敬翱诳煞譃槿缦?個部分：(1)初始代碼區(qū)：用于打開并顯示出原始的匯編源文件；(2)簡化代碼區(qū)：用于顯示簡化后的代碼；(3)分塊信息區(qū)：用于顯示優(yōu)化前后基本塊的信息。

繪圖窗口用于顯示優(yōu)化前后的效果對比，因此，直接將窗口一分為二，分別繪制跳轉(zhuǎn)流程圖。整個軟件工具的界面框圖如圖2所示。

圖2　軟件界面結(jié)構(gòu)圖

3.1基本窗口的實現(xiàn)

初始代碼區(qū)中需要完成打開并顯示源代碼操作。鑒于文件的特點和人性化考慮，此區(qū)域中采用單擊按鈕彈出文件瀏覽窗口完成文件選擇，并顯示文件路徑及分行顯示打開的匯編代碼源文件。此外，基于簡化預(yù)處理程序算法，簡化代碼區(qū)中將完成的是將展平后的源匯編文件進(jìn)行簡化，得到只有指令和標(biāo)號行的偽匯編代碼，以方便代碼掃描和分塊。分塊信息區(qū)中則顯示包括優(yōu)化前后的基本塊的信息及其跳轉(zhuǎn)關(guān)系。基本信息包括基本塊塊號、入口信息、出口信息、塊長度、下一跳地址。

3.2跳轉(zhuǎn)流程圖的繪制

DSP匯編程序跳轉(zhuǎn)流程圖的繪制在一個獨立對話框窗口創(chuàng)建，該窗口與流程圖生成按鈕進(jìn)行關(guān)聯(lián)[15]。繪制思想是，2次遍歷存放跳轉(zhuǎn)信息的二維數(shù)組，第一次只是繪制塊節(jié)點，即只要發(fā)現(xiàn)一個新的塊，就將其繪制出來，其形狀和大小以及當(dāng)中的字符顯示均可自己設(shè)定。這樣，一次遍歷完后就將所有的塊都繪制在了窗口中。第二次遍歷則是單純地繪制跳轉(zhuǎn)關(guān)系，按照傳統(tǒng)的流程圖繪制習(xí)慣，從上往下跳轉(zhuǎn)的繪制在右邊，將自身跳轉(zhuǎn)和從下往上跳轉(zhuǎn)的繪制在左邊。最后，將整個繪圖的部分包含在一個文件中，分別用優(yōu)化前后的分塊表所對應(yīng)的二維矩陣去調(diào)用這個文件，得到優(yōu)化前后的跳轉(zhuǎn)流程圖。

3.3運行實例

選擇DSP開發(fā)的FFT變換程序作為軟件運行的實例。該FFT程序中主要由4個函數(shù)組成：一個主函數(shù)、一個初始化FFT函數(shù)、一個FFT執(zhí)行函數(shù)和一個生成波形的函數(shù)，主函數(shù)分別調(diào)用另外3個函數(shù)。

圖3則為根據(jù)優(yōu)化前的分塊表信息繪制的FFT程序跳轉(zhuǎn)流程圖，以及根據(jù)簡化后的分塊表信息繪制的跳轉(zhuǎn)流程圖。

圖3　優(yōu)化前后的FFT程序跳轉(zhuǎn)流程圖

4　總結(jié)

本文研究了DSP匯編程序基本塊劃分與優(yōu)化方法，并設(shè)計實現(xiàn)了基本塊劃分與優(yōu)化軟件。該軟件通過對匯編程序進(jìn)行精簡，去除匯編程序中與運行無關(guān)的解釋和聲明信息；再對精簡后程序進(jìn)行基本塊劃分，保存劃分出的基本塊的結(jié)構(gòu)信息，并將其作為DSP程序控制流錯誤檢測的依據(jù)；然后，在分塊表上進(jìn)行函數(shù)返回優(yōu)化、函數(shù)調(diào)用優(yōu)化和循環(huán)優(yōu)化，減少基本塊的數(shù)量；最后根據(jù)優(yōu)化前后的基本塊信息，繪制程序的跳轉(zhuǎn)流程圖。該DSP匯編程序文件結(jié)構(gòu)簡單、格式整齊，在實現(xiàn)所需功能的同時，具有代碼精簡、穩(wěn)定性好、空間復(fù)雜度小等優(yōu)點。

參考文獻(xiàn)(References)：

[1]賀興華，肖山竹，張路，等.空間DSP信息處理系統(tǒng)存儲器SEU加固技術(shù)研究[J].宇航學(xué)報，2010，31(2)：472-477.

[2]王大慶，劉曉旭，王宇，等.基于軟件的星載DSP減緩單粒子效應(yīng)措施研究[J].空間電子技術(shù)，2013，38(1):40-43.

[3]王浩.DSP輻射效應(yīng)分析及測試方法研究[D].西安：西安電子科技大學(xué)，2013.

[4]譚蘭芳.面向軟錯誤的故障恢復(fù)和驗證技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2013.

[5]BAUMANN RC.Soft errors in commercial semiconductor technology:overview and scaling trends[J].IEEE 2002 Reliability Physics Tutorial Notes-Reliability Fundamentals,2002,12(1):1-14.

[6]李建立，譚慶平，譚蘭芳，等.一種基于虛擬基本塊和格式化標(biāo)簽的控制流檢測方法[J].計算機(jī)學(xué)報,2014,37(11):2287-2296.

[7]徐建軍，譚慶平，李建立，等.一種基于格式化標(biāo)簽的可擴(kuò)展控制流檢測方法[J].計算機(jī)研究與發(fā)展,2011,48(4):638- 646.

[8]吳艷霞.基于匯編語言的控制流錯誤檢測算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2008.

[9]Mostafa Jafari-Nodoushan，Seyed Ghassem Miremadi，Alireza Ejlali.Control-flow checking using branch instructions[C].2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing.

[10]刑克飛.星載信號處理平臺單粒子效應(yīng)檢測與加固技術(shù)研究[D].長沙：國防科技大學(xué)，2007

[11]黃振遠(yuǎn).一種星載計算機(jī)控制流件檢錯技術(shù)的研究與實現(xiàn)[D].哈爾濱：哈爾濱工業(yè)大學(xué),2006

[12]Oh,N.,Shirvani,P.P.Control-flow checking by software signatures[J],IEEE Transactions on Reliability,2002，51(1)：11-122.

[13]Bolchini C,Miele A,Rebaudengo M,etc.Software and hardware techniques for SEU detection in IP processors[J].Journal of Electronic Testing,2008,24(1):35-44.

[14]張平，李清寶，崔晨.基于自動路徑驅(qū)動的動態(tài)控制流恢復(fù)算法[J].計算機(jī)工程,2013,39(8):77-82.

[15]孫永新，吳家培，閆大順.基于基本塊標(biāo)識方法的控制流圖生成器設(shè)計[J].計算機(jī)應(yīng)用與軟件,2010,27(5):158-161.

(責(zé)任編輯：劉劃英文審校：王云雁)

收稿日期：2015-03-27

基金項目：國家自然科學(xué)基金(項目編號：61371024)、航空科學(xué)基金(項目編號：2013ZD53051)、國防"973"項目、總裝預(yù)研基金、航天支撐技術(shù)基金、中航產(chǎn)學(xué)研項目(項目編號：cxy2013XGD14)。

作者簡介：周國昌(1978-)，男，遼寧撫順人，高級工程師，博士，主要研究方向：計算機(jī)體系統(tǒng)結(jié)構(gòu)、星載ASIC 設(shè)計等。

文章編號：2095-1248(2016)02-0052-07

中圖分類號：TP319

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.2095-1248.2016.02.010

Basic blocks division optimization with DSP assemble and it’s software implementation

ZHOU Guo-chang1,JU Ting1,LAI Xiao-ling1,ZHU Qi1,WANG Xiang-tao2,YU Deng-yun3,GUO Yang-ming2

(1.Academy of Space Technology(Xi’an),Xi’an 710100，China;2.School of Computer Science and Technology,Northwestern Polytechnical University,Xi’an 710072，China;3.The Science and Technology Committee,China Aerospace Science and Technology Corp.,Beijing 100048，China)

Abstract：In order to meet the needs of DSP soft error detection in space environment,the DSP assembler basic block division and optimization method is presented,and a software tool based on the proposed method is designed and implemented.With the method,the assembly codes are firstly simplified to pseudo-codes only containing instructions and their labels.Afterwards,the basic blocks are segmented with the pseudo assembly codes.Finally,the optimized basic blocks are achieved with three times optimization.Moreover,with the information of basic blocks,the flow jump charts before and after optimization are drawn respectively.A certain DSP assembler can be divided into a collection of basic blocks with the tool of the software,and the structure information of each basic block are extracted simultaneously.The application shows the software has some merits,such as concise code,good stability,small space complexity,etc.It will be very valuable in application for DSP soft error detection.

Key words：basic block division;optimization;assembler;DSP