10002601 任珊珊11答辩ppt_任珊珊

1、基于LLVM的程序切片系统答辩人：任珊珊 1002601导师：张迎周 教授2014年6月7日01目录页选题02设计contents03实现1、选题背景在程序分析测试时，由于程序段代码量大，针对不同程序变量、接口的测试分析起 来较为困难，费时又费力，而且还容易出错。问题：当一个大的计算机程序被分解成一个个较小的程序片以后，很容易被构造、理解和维护。我们需要一些用于程序分解的技术和方法，在这些技术中程序切片起到了无可替代的作用解决：1、选题发展（1）基于数据流方程的程序切片阶段M.Weiser （基于CFG的数据流方程）（2）基于依赖图的程序切片阶段K.J.Ottenstein（基于程序依赖图）、

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

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

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

5、法根据依赖关系构造成图系统依赖图（SDG）可达性计算切片生成器控制依赖关系数据依赖关系源程序2、设计理论支撑工具（Low Level Virtual Machine ），可以作LLVM为多种语言编译器的。虚拟指令集高层结构类型系统核心库分析库目标处理库转换库代码生成库运行库基本工具编译工具后端工具调试工具原子类型衍生类型单指令内函数工 具集成库中间代码LLVM编译系统2、设计理论支撑工具LLVM工具及相互关系lli直接运行Llvm-disLlvm-as调试工具bugpoint llvm-extract llvm- bcanalyzer.b文件.ll文件.llc目标处理器汇编代码gcca和gcc

6、ldLlvmg和llvmg+被调用.h，.c，.cpp文件其他工具llvm-link、llvm-ar llvm-nmllvm-ranlibllvm-prof、llvm-ld2、设计理论支撑工具LLVMIRLLVMIRC代码后端代码文件C+代码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