孟凡奇

摘 要：循環(huán)語句的執(zhí)行次數(shù)對程序的執(zhí)行時間是有影響的，通常循環(huán)次數(shù)越多，程序執(zhí)行時間越長。因此，在最差情況執(zhí)行時間分析中通常需要指明程序循環(huán)語句的執(zhí)行次數(shù)上限。本文簡要分析使用局部約束與全局約束標注循環(huán)上限對最差情況執(zhí)行時間分析結(jié)果的影響。

關(guān)鍵詞：最差情況執(zhí)行時間；循環(huán)上界；局部約束；全局約束

眾所周知，循環(huán)次數(shù)對執(zhí)行時間是有影響的，通常循環(huán)次數(shù)越多，程序執(zhí)行時間越長。因此，靜態(tài)最差情況執(zhí)行時間（Worst-case Execution Time，WCET）分析通常都需要知道（自動分析或人工標注）循環(huán)上界，以便使WCET估計值更精確[1]。本文將探尋使用“局部”或“全局”約束法標注循環(huán)上界會對程序的WCET分析有何影響，據(jù)此，我們可以決定何種情況下使用何種方法。

1 局部約束與全局約束

“局部”循環(huán)邊界是指循環(huán)語句執(zhí)行1次，其循環(huán)體可能的執(zhí)行次數(shù)范圍?！叭帧毖h(huán)邊界是指從程序開始運行到結(jié)束，循環(huán)語句的循環(huán)體可能的全部執(zhí)行次數(shù)范圍。

以下面的代碼為例，第1行for語句的“局部”和“全局”循環(huán)邊界都是[0，5]。第2行for語句的局部循環(huán)邊界是[0，5]，全局循環(huán)邊界是[0，25]。

需要說明的是，由于WCET計算的是最差情況，因此，通常僅需要提供循環(huán)上界。我們可以使用“局部”約束法或“全局”約束法為計算WCET的整數(shù)線性規(guī)劃提供所需的循環(huán)上界的表達式。局部約束法使用局部循環(huán)上界，分析工具會將局部循環(huán)上界轉(zhuǎn)換成內(nèi)外層語句執(zhí)行次數(shù)的整數(shù)倍數(shù)關(guān)系。以上面的代碼為例，如果第2個for循環(huán)的循環(huán)邊界使用局部約束法進行標注，則會生成表達式“l(fā)ine2-5line1=0”，即第1行每執(zhí)行1次，第2行執(zhí)行5次。而全局約束使用全局循環(huán)邊界，若第2個for使用全局約束，則會生成表達式“l(fā)ine2=25”。

多數(shù)情況下，由于局部循環(huán)邊界易于獲取，所以局部約束法是較為常見的標注方式。然而，情況并非如此簡單。對于上下文敏感的循環(huán)，尤其是非正交多重嵌套循環(huán)，獲取內(nèi)循環(huán)的局部循環(huán)邊界也并不容易。

2 全局約束與非正交循環(huán)

若嵌套循環(huán)中內(nèi)層循環(huán)的執(zhí)行次數(shù)完全或部分地依賴于外層循環(huán)能夠直接修改的變量，則稱此嵌套循環(huán)為“非正交”嵌套循環(huán)。

以下面的程序片段為例，第10行的while語句的局部循環(huán)執(zhí)行次數(shù)既與外層循環(huán)的控制變量i有關(guān)，同時還與全局變量數(shù)組a有關(guān)。出于對安全的考慮，此類非正交多重嵌套循環(huán)在標注內(nèi)循環(huán)的循環(huán)邊界時，往往采用局部循環(huán)上界，即所有可能情況下的局部最大循環(huán)次數(shù)。例如，第10行while語句的局部循環(huán)上界是“9”。這樣一來，內(nèi)層while的全局執(zhí)行次數(shù)會被記為小于等于9×9=81次。而其實際的最大全局執(zhí)行次數(shù)為9+8+7+6+5+4+3+2+1=45次。于是，WCET估計值被嚴重高估了。

要獲得更精確的WCET估計值，可以使用全局約束法標注非正交多重嵌套循環(huán)的循環(huán)邊界。從表1中可以看出，使用全局約束可以獲得比使用局部約束更精確的WCET估計值。程序fac.c來自于M?lardalen大學(xué)的WCET基準程序集。

可以采用“插樁→運行”的動態(tài)方法獲取循環(huán)的全局執(zhí)行次數(shù)。首先，生成待處理程序的抽象語法樹；然后，在抽象語法樹中尋找循環(huán)語句節(jié)點；接著，在每一個循環(huán)語句節(jié)點的第一個子節(jié)點之前插裝探針，用于輸出該循環(huán)語句在原源程序中的行號；然后，將插樁后的抽象語法樹還原為源程序；最后，這個已經(jīng)插樁了的源程序獲得各循環(huán)語句的執(zhí)行次數(shù)。此方法的優(yōu)點是易于實現(xiàn)、效率較高。但缺點是必須提供最差輸入，否則獲得的循環(huán)執(zhí)行次數(shù)未必是最差情況下的全局循環(huán)上界。

3 結(jié)束語

局部約束適用于循環(huán)上界識別較為容易的正交循環(huán)。全局約束適用于非正交循環(huán)的內(nèi)循環(huán)語句，可以獲得相較于局部約束更為精確的WCET估計值。因此，當(dāng)程序中的嵌套循環(huán)是正交的，建議使用局部約束標注循環(huán)上界，否則建議使用全局約束。

[參考文獻]

[1]呂鳴松，關(guān)楠，王義.面向WCET估計的Cache分析研究綜述[J].軟件學(xué)報，2014，25（2）：179-199.

[2]Li X，Liang Y，Mitra T，et al.Chronos：A timing analyzer for embedded software[J].Science of Computer Programming，2007， 69（1）：56-67.

[3]呂鳴松.實時系統(tǒng)最壞情況執(zhí)行時間分析技術(shù)的研究[D].東北大學(xué)， 2010.