快速程序流分析方法的研究與應(yīng)用.pdf

1、衡量系統(tǒng)實(shí)時(shí)性的最重要的參數(shù)是任務(wù)的最壞情況執(zhí)行時(shí)間(WCET)。WCET分析的目的在于得到任務(wù)執(zhí)行時(shí)間的上界約束，這需要綜合考慮系統(tǒng)的軟硬件特征。由于WCET的動(dòng)態(tài)測(cè)量方法不能保證估計(jì)結(jié)果是安全的，所以現(xiàn)在一般學(xué)者都致力于靜態(tài)分析方法的研究。隨著軟件規(guī)模及其復(fù)雜性的不斷增長(zhǎng)，使得快速地獲得WCET估計(jì)值更加困難。 在WCET程序流分析中，本文依據(jù)C的語言特點(diǎn)，給出了從抽象語法樹到程序控制流圖的構(gòu)造，由程序控制流圖到靜態(tài)單賦值形

2、式的轉(zhuǎn)變。依據(jù)靜態(tài)單賦值形式的控制流圖得出數(shù)據(jù)依賴和數(shù)據(jù)依賴關(guān)系，然后就可以構(gòu)造程序依賴圖。對(duì)程序依賴圖的擴(kuò)展得到系統(tǒng)依賴圖，利用圖的可達(dá)性算法來對(duì)程序進(jìn)行切片。本文還給出了一種不是基于依賴圖的簡(jiǎn)單程序切片算法，該算法適合對(duì)程序中所有條件語句計(jì)算切片。經(jīng)過程序切片后，采用抽象解釋來自動(dòng)導(dǎo)出程序流中循環(huán)迭代界限、不可行路徑等約束信息，避免了手工標(biāo)注。 依據(jù)上述給出的程序流分析方法，本文給出了程序流分析工具的設(shè)計(jì)架構(gòu)。實(shí)驗(yàn)結(jié)果表明，