1、,基于LLVM的程序切片系統(tǒng),2014年6月7日,目錄頁(yè),contents,1、選題,問(wèn)題：,背景,當(dāng)一個(gè)大的計(jì)算機(jī)程序被分解成一個(gè)個(gè)較小的程序片以后，很容易被構(gòu)造、理解和維護(hù)。,在程序分析測(cè)試時(shí)，由于程序段代碼量大，針對(duì)不同程序變量、接口的測(cè)試分析起來(lái)較為困難，費(fèi)時(shí)又費(fèi)力，而且還容易出錯(cuò)。,解決：,我們需要一些用于程序分解的技術(shù)和方法，在這些技術(shù)中程序切片起到了無(wú)可替代的作用,1、選題,發(fā)展,（1）基于數(shù)據(jù)流方程的程序切片階段,（2）基于依賴圖的程序切片階段,（3）面向?qū)ο蟪绦蚯衅A段,（4）程序切片發(fā)展“百花齊放”階段,M.Weiser （基于CFG的數(shù)據(jù)流方程）,K.J.Ottenste

2、in（基于程序依賴圖）、S.Horwitz（前向切片）等,M.J.Horrald（擴(kuò)充的依賴圖）、D.Liang和Z.Chen（面向?qū)ο髣?dòng)態(tài)切片）,削片、砍片、數(shù)據(jù)切片、層次切片和無(wú)定型切片,2、設(shè)計(jì)理論,基本思想,M.Weiser等人將只與某個(gè)輸出有關(guān)的語(yǔ)句和謂詞所構(gòu)成的程序成為程序的一種靜態(tài)切片（static slice），并提出了基于CFG的計(jì)算程序切片的算法。,他定義的程序切片是通過(guò)對(duì)初始程序刪除零條或多條語(yǔ)句得到的可執(zhí)行程序。切片準(zhǔn)則是二元組，其中V表示在n定義或使用變量的集合，n表示程序中的某個(gè)點(diǎn)。關(guān)于切片準(zhǔn)則的程序切片是程序P的語(yǔ)句的一個(gè)子集S，它必須滿足：,（1）S必須是一個(gè)有

3、效程序； （2）對(duì)一個(gè)給定的輸入，P中斷時(shí)，S也中斷，無(wú)論何時(shí)，與S相關(guān)的語(yǔ)句被執(zhí)行時(shí)，計(jì)算V中所有變量的值都必須是相同的。,2、設(shè)計(jì)理論,依賴關(guān)系,在一個(gè)源代碼中，對(duì)于一個(gè)變量的有直接影響關(guān)系的稱為數(shù)據(jù)依賴，而對(duì)一個(gè)變量有間接影響關(guān)系的稱為控制依賴，比如出現(xiàn)if，while的時(shí)候。,第4條語(yǔ)句的i變量和第7條語(yǔ)句i變量有著直接影響關(guān)系，所以其存在數(shù)據(jù)依賴關(guān)系,第6條語(yǔ)句存在if判斷語(yǔ)句，所以對(duì)i變量的語(yǔ)句存在間接依賴，我們稱之為控制依賴關(guān)系,2、設(shè)計(jì)理論,依賴圖的構(gòu)造,目前的程序切片大都是以SDG為基礎(chǔ)，在其上利用圖的可達(dá)性算法獲得的。,SDG包含許多過(guò)程依賴圖（ProcedureDepen

4、dence Graph，PDG），每一個(gè)PDG對(duì)應(yīng)程序中的一個(gè)過(guò)程。PDG由點(diǎn)和邊組成，其中點(diǎn)代表語(yǔ)句或判定表達(dá)式，邊又分為數(shù)據(jù)依賴邊和控制依賴邊。,基于數(shù)據(jù)流分析的算法：確定直接相關(guān)變量與語(yǔ)句，確定間接相關(guān)變量和語(yǔ)句的方程,圖的可達(dá)性算法：找出所有從依賴圖的入口節(jié)點(diǎn)到切片準(zhǔn)則節(jié)點(diǎn)的所有路徑，把這些路徑所經(jīng)過(guò)的節(jié)點(diǎn)標(biāo)記出來(lái)，其構(gòu)成的集合就是關(guān)于切片準(zhǔn)則的一個(gè)依賴圖切片。,2、設(shè)計(jì)理論,2,5,4,6,7,圖中可以看出，對(duì)于i變量，我們根據(jù)控制依賴和數(shù)據(jù)依賴關(guān)系構(gòu)造成簡(jiǎn)單的依賴圖。其中結(jié)點(diǎn)為父子關(guān)系的為控制依賴關(guān)系，節(jié)點(diǎn)是虛線的是數(shù)據(jù)依賴關(guān)系。,依賴圖的構(gòu)造的例子,2、設(shè)計(jì)理論,設(shè)計(jì)流程圖,源程

5、序,數(shù)據(jù)依賴關(guān)系,控制依賴關(guān)系,系統(tǒng)依賴圖（SDG）,切片生成器,基于數(shù)據(jù)/控制流分析算法,可達(dá)性計(jì)算,根據(jù)依賴關(guān)系構(gòu)造成圖,2、設(shè)計(jì)理論,支撐工具,LLVM （Low Level Virtual Machine ），可以作為多種語(yǔ)言編譯器的后臺(tái)。,LLVM編譯系統(tǒng),中間代碼,集 成 庫(kù),工 具,虛擬指令集,高層結(jié)構(gòu),類型系統(tǒng),核心庫(kù),分析庫(kù),轉(zhuǎn)換庫(kù),代碼生成庫(kù),運(yùn)行庫(kù),目標(biāo)處理庫(kù),基本工具,編譯工具,調(diào)試工具,后端工具,單指令,內(nèi)函數(shù),原子類型,衍生類型,2、設(shè)計(jì)理論,支撐工具,LLVM工具及相互關(guān)系,2、設(shè)計(jì)理論,支撐工具,LLVM編譯流程,3、運(yùn)行演示,執(zhí)行步驟,1編譯過(guò)程： 在LLVMSlicer-build目錄下依次執(zhí)行指令： （1）cmake . （2）make,2執(zhí)行過(guò)程： 在LLVMSlicer-build-src目錄下依次執(zhí)行指令： （1）opt load ./LLVMSliser.so create-hammock-cfg slice-inter calc.bc o calc1.bc （2）sh ./process.sh 源程序名 切片變量,3