毕业答辩-基于LLVM的程序切片系统

1、,基于LLVM的程序切片系统,2014年6月7日,目录页,contents,1、选题,问题：,背景,当一个大的计算机程序被分解成一个个较小的程序片以后，很容易被构造、理解和维护。,在程序分析测试时，由于程序段代码量大，针对不同程序变量、接口的测试分析起来较为困难，费时又费力，而且还容易出错。,解决：,我们需要一些用于程序分解的技术和方法，在这些技术中程序切片起到了无可替代的作用,1、选题,发展,（1）基于数据流方程的程序切片阶段,（2）基于依赖图的程序切片阶段,（3）面向对象程序切片阶段,（4）程序切片发展“百花齐放”阶段,M.Weiser （基于CFG的数据流方程）,K.J.Ottenste

2、in（基于程序依赖图）、S.Horwitz（前向切片）等,M.J.Horrald（扩充的依赖图）、D.Liang和Z.Chen（面向对象动态切片）,削片、砍片、数据切片、层次切片和无定型切片,2、设计理论,基本思想,M.Weiser等人将只与某个输出有关的语句和谓词所构成的程序成为程序的一种静态切片（static slice），并提出了基于CFG的计算程序切片的算法。,他定义的程序切片是通过对初始程序删除零条或多条语句得到的可执行程序。切片准则是二元组，其中V表示在n定义或使用变量的集合，n表示程序中的某个点。关于切片准则的程序切片是程序P的语句的一个子集S，它必须满足：,（1）S必须是一个有

3、效程序； （2）对一个给定的输入，P中断时，S也中断，无论何时，与S相关的语句被执行时，计算V中所有变量的值都必须是相同的。,2、设计理论,依赖关系,在一个源代码中，对于一个变量的有直接影响关系的称为数据依赖，而对一个变量有间接影响关系的称为控制依赖，比如出现if，while的时候。,第4条语句的i变量和第7条语句i变量有着直接影响关系，所以其存在数据依赖关系,第6条语句存在if判断语句，所以对i变量的语句存在间接依赖，我们称之为控制依赖关系,2、设计理论,依赖图的构造,目前的程序切片大都是以SDG为基础，在其上利用图的可达性算法获得的。,SDG包含许多过程依赖图（ProcedureDepen

4、dence Graph，PDG），每一个PDG对应程序中的一个过程。PDG由点和边组成，其中点代表语句或判定表达式，边又分为数据依赖边和控制依赖边。,基于数据流分析的算法：确定直接相关变量与语句，确定间接相关变量和语句的方程,图的可达性算法：找出所有从依赖图的入口节点到切片准则节点的所有路径，把这些路径所经过的节点标记出来，其构成的集合就是关于切片准则的一个依赖图切片。,2、设计理论,2,5,4,6,7,图中可以看出，对于i变量，我们根据控制依赖和数据依赖关系构造成简单的依赖图。其中结点为父子关系的为控制依赖关系，节点是虚线的是数据依赖关系。,依赖图的构造的例子,2、设计理论,设计流程图,源程

5、序,数据依赖关系,控制依赖关系,系统依赖图（SDG）,切片生成器,基于数据/控制流分析算法,可达性计算,根据依赖关系构造成图,2、设计理论,支撑工具,LLVM （Low Level Virtual Machine ），可以作为多种语言编译器的后台。,LLVM编译系统,中间代码,集 成 库,工 具,虚拟指令集,高层结构,类型系统,核心库,分析库,转换库,代码生成库,运行库,目标处理库,基本工具,编译工具,调试工具,后端工具,单指令,内函数,原子类型,衍生类型,2、设计理论,支撑工具,LLVM工具及相互关系,2、设计理论,支撑工具,LLVM编译流程,3、运行演示,执行步骤,1编译过程： 在LLVMSlicer-build目录下依次执行指令： （1）cmake . （2）make,2执行过程： 在LLVMSlicer-build-src目录下依次执行指令： （1）opt load ./LLVMSliser.so create-hammock-cfg slice-inter calc.bc o calc1.bc （2）sh ./process.sh 源程序名 切片变量,3